AcWing831.KMP字符串 题目链接

题目如下:

ac831.jpg

KMP是真勾八难，折腾了一晚上才勉强整明白，特别是推导next数组的步骤，看了好几篇博客代码都不一样，在纸上跟着推了一遍才看明白。


(偷一波社区dalao的推导，链接在这)
最后AC的代码和注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    //为了方便从1开始索引
    cin >> n >> p + 1 >> m >> s + 1;
    /*
    该循环推导next数组
        next[]数组含义:
            next[i]中存储的值为 [0,i]的最长公共前后缀大小 (即前缀的尾部索引)
    */

    //注意 j 从 0 开始，因为判断时取p[j+1]
    for(int i=2,j=0;i<=n;i++){
        /*
        如果当前p[i]!=p[j+1]的话,此时j为上一步(或为0),将next[j]赋给j
        该while循环在p[i]==p[j+1]或j==0(即退无可退，上一步只能从1开始匹配)时退出
        */
        while(j&&p[i]!=p[j+1]) j = ne[j];
        //代码执行到这，j+1有可能等于j的公共前后缀未索引，也有可能j=0
        //判断一下当当前字符p[i]等于ne[j]公共前后缀+1字符的话，ne[i]的公共前后缀长度+1
        if(p[i]==p[j+1]) j++;
        //当然也有可能是0
        ne[i] = j;
    }
    /*
    该循环在S串中寻找子串P，返回首索引
    */
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        //与求next数组相同，如果当前s[i]!=p[j+1]的话，寻找[1,j]的公共前后缀长度赋给j
        //如果退无可退的话，j这一步之后会等于0，即下一次循环子串从头开始匹配
        while (j && s[i] != p[j + 1]) j = ne[j];
        //如果字符相同的话，子串的j指针继续往后走
        if (s[i] == p[j + 1]) j ++ ;
        //j会一直回溯或前进，当j和p的字符数相等时，说明已经匹配完成
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
    return 0;
}