输入

"ababab","abababab"

输出

示例2

输入

"abab","abacabab"

输出

备注:

空间O(n)时间O(n)的算法

算法知识视频讲解

gywy

模板题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string s, string t) {
        // write code here
        int n = s.size(), m = t.size();
        s = ' ' + s, t = ' ' + t;
        int ne[n + 10];
        memset(ne, 0, sizeof ne);
        for (int i = 2, j = 0; i <= n; i ++) {
            while (j && s[j + 1] != s[i]) j = ne[j];
            if (s[j + 1] == s[i]) j ++;
            ne[i] = j;
        }
        int ans = 0;
        for (int i = 1, j = 0; i <= m; i ++) {
            while (j && s[j + 1] != t[i]) j = ne[j];
            if (s[j + 1] == t[i]) j ++;
            if (j == n) ans ++;
        }
        return ans;
    }
};

发表于 2021-02-16 16:59:59 回复(0)

C/C++

泡泡HUB

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
int kmp(char* S, char* T ) 
{
    // write code here
    int a,i,j,n=0;
    a=strlen(S);
    for(i=0;T[i]!='\0';i++)
    {
        for(j=0;j<a;j++)
        {
            if(S[j]!=T[i+j])
            {
                break;
            }
        }
        if(j>=a)
        {
            n++;
        }
    }
    return n;
}

发表于 2021-02-02 23:50:52 回复(0)

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 回复(0)