kmp算法

[编程题]kmp算法

热度指数：31116 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次

数据范围： $1 \le len(S) \le 500000, 1 \le len(T) \le 1000000$

要求：空间复杂度 $O(len(S))$ ，时间复杂度 $O(len(S)+len(T))$

示例1

输入

"ababab","abababab"

输出

示例2

输入

"abab","abacabab"

输出

算法知识视频讲解

JavaScript

splwany

function kmp(S, T) {
    if (!S || !T || T.length < S.length) return 0;
    const next = getNext(S);
    return getCount(next, S, T);
}
function getNext(needle) {
    const next = Array(needle.length).fill(0);
    for (let i = 1, j = 0; i < needle.length; ++i) {
        while (j > 0 && needle[i] !== needle[j]) j = next[j - 1];
        if (needle[i] === needle[j]) j++;
        next[i] = j;
    }
    return next;
}
function getCount(next, needle, haystack) {
    let count = 0;
    for (let i = 0, j = 0; i < haystack.length; i++) {
        while (j > 0 && haystack[i] !== needle[j]) j = next[j - 1];
        if (haystack[i] === needle[j]) ++j;
        if (j === needle.length) {
            count++;
            j = next[j - 1];
        }
    }
    return count;
}

发表于 2021-04-22 15:34:03 回复(1)

JavaScript

别卷啦！

字符串匹配的KMP算法类似滑动窗口的实现方式

function kmp( S ,  T) {
    // write code here
    //待优化：
	let sum = 0,len= S.length
    for(let i = 0;i<T.length;i++){
        if(S == T.slice(i,len+i)){
           ++ sum 
        }
    }
    return sum
}

发表于 2021-01-15 12:39:41 回复(3)