AcWing 831. KMP字符串

2021-05-16 23:30

阅读：338

标签：ble ios 匹配 next ++ 不能 print nbsp ext

https://www.acwing.com/problem/content/833/

#include using namespace std;
const int N = 10010, M = 100010;
int n, m;
int ne[N];
char s[M], p[N];
int main() {
    cin >> n >> p + 1 >> m >> s + 1;
    //求next过程
    //i从2开始，因为next[1]=0,如果第一个字母失败了，只能从0开始
    for (int i = 2, j = 0; i  ) {
        while (j && p[i] != p[j + 1])
            j = ne[j];
        if (p[i] == p[j + 1])
            j ++ ;
        ne[i] = j;
    }
    //kmp匹配过程
    for (int i = 1, j = 0; i  ) {
        while (j && s[i] != p[j + 1])    //当j没有退回起点，并且当前的s[i]不能和下一个j的位置匹配
            j = ne[j];//移动，保证之前的相等  直到匹配位置，或者j已经到开头了
        if (s[i] == p[j + 1]) //如果已经匹配了
            j ++ ;  //j往下移动
        if (j == n) {//说明匹配成果
            printf("%d ", i - n+1);
            j = ne[j];
        }
    }
    return 0;
}

AcWing 831. KMP字符串

标签：ble ios 匹配 next ++ 不能 print nbsp ext

原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11790107.html

上一篇：windows下ffmpeg批量转码

下一篇：浅谈C#委托

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 831. KMP字符串
文章链接：http://soscw.com/index.php/essay/86468.html

亲，登录后才可以留言！

AcWing 831. KMP字符串

评论

热门文章

推荐文章

最新文章

置顶文章