首页 > 试题广场 > kmp算法
[编程题]kmp算法
  • 热度指数:208 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给你一个非空模板串S,一个文本串T,问S在T中出现了多少次
示例1

输入

"ababab","abababab"

输出

2
示例2

输入

"abab","abacabab"

输出

1

备注:
空间O(n)时间O(n)的算法
模板题
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)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 计算模板串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)
字符串匹配的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)