关于kmp算法

2020-12-13 16:41

阅读：368

标签：ring log href mp算法 clu ++ 匹配 space lan

字符串匹配算法简称kmp

日常安利大佬博客（真的是一篇很好的文章）

技术图片

觉得百度百科讲的也挺好

就是给出两个字符串a， b

求b在a中的所有位置

next数组：代表当前字符之前的字符串中，有多大长度的相同前缀后缀（都指自己本身）

技术图片

对于求next数组我们考虑b字符串自己匹配自己

        lb = strlen (b + 1);
    for (int i = 2; i ) {
        while(j && b[j + 1] != b[i]) j = next[j];
        if(b[j + 1] == b[i]) j++;
        next[i] = j;
    }

例题

#include 
#include 
#include using namespace std;
int next[2333333];
int la, lb, j;
char a[2333333], b[2333333];
int main () {
    cin >> a + 1;
    cin >> b + 1;
    la = strlen (a + 1);
    lb = strlen (b + 1);
    for (int i = 2; i ) {
        while(j && b[j + 1] != b[i]) j = next[j];
        if(b[j + 1] == b[i]) j++;
        next[i] = j;
    }
    j = 0;
    for (int i = 1; i ) {
        while (j && b[j + 1] != a[i]) 
            j = next[j];
        if (b[j + 1] == a[i])j++;
        if (j == lb) {
            printf ("%d\n", i - lb + 1);
            j = next[j];
        }
    }
    for (int i = 1; i ) 
        printf ("%d ", next[i]);
    return 0;
}

关于kmp算法

标签：ring log href mp算法 clu ++ 匹配 space lan

原文地址：https://www.cnblogs.com/yanxiujie/p/11621298.html

上一篇：JavaScript 语法:松软科技前端教程

下一篇：ABP开发手记14 - 更新多语言

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：关于kmp算法
文章链接：http://soscw.com/essay/36415.html

亲，登录后才可以留言！

关于kmp算法

评论

热门文章

推荐文章

最新文章

置顶文章