KMP（模板）

首先：KMP的模板为：

void get_next(char *a, int *nex) {
    nex[1] = 0;
    for (int i = 2, j = 0; i <= len; i++) {
        while (j > 0 && a[i] != a[j + 1])j = nex[j];
        if (a[i] == a[j + 1])j++;
        nex[i] = j;
    }
    return;
}

int KMP(char *a, char *b) {//b为母串
    for (int i = 1, j = 0; i <= strlen(b + 1); i++) {
        while (j > 0 && (j == strlen(a + 1) || b[i] != a[j + 1]))j = nex[j];
        if (b[i] == a[j + 1])j++;
        f[i] = j;
        //若a在b中出现,，返回出现的位置
        //if(f[i]==strlen(a+1)){return i-strlen(a);}
    }
    return 1;
}

例题：2018 UESTC Training for Search Algorithm & String——L主楼

题意：求字符串中的最短循环节，并输出该循环节

KMP最小循环节、循环周期：
定理：假设S的长度为len，则S存在最小循环节，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。
（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。
（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。

注意这里的len是原字符串的len+1；

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int T, len;
 6 char s[100000 + 5];
 7 int nex[100000 + 5];
 8 
 9 void get_next(char* p, int next[]){
10     int pLen = strlen(p) + 1;//要求循环节长度时这里才+1
11     next[0] = -1;
12     int k = -1;
13     int j = 0;
14     while (j < pLen - 1){  
15         if (k == -1 || p[j] == p[k]){
16             ++j;++k;
17             if (p[j] != p[k])
18                 next[j] = k;
19             else
20                 next[j] = next[k];
21         }
22         else{
23             k = next[k];
24         }
25     }
26 }
27 
28 int kmp(char* s, char* p){
29     int i = 0;
30     int j = 0;
31     int sLen = strlen(s);
32     int pLen = strlen(p);
33     while (i < sLen && j < pLen){
34             //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
35         if (j == -1 || s[i] == p[j]){
36             i++;
37             j++;
38         }
39         else{
40             //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
41             //next[j]即为j所对应的next值        
42             j = nex[j];
43         }
44     }
45     if (j == pLen)
46         return i - j;
47     else
48         return -1;
49 }
50 
51 int main() {
52     scanf("%d", &T);
53     while (T--) {
54         memset(nex, 0, sizeof(nex));
55         scanf("%d", &len);
56         scanf("%s", s);
57         len = strlen(s);
58         get_next(s, nex);
59         printf("%d
", len - nex[len]);
60         for (int i = 0; i < len - nex[len]; i++)
61             printf("%c", s[i]);
62         printf("
");
63     }
64     return 0;
65 }

HDU1711（数字KMP）

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int T, len;
 6 int len1, len2;
 7 int s1[1000000 + 5];
 8 int s2[1000000 + 5];
 9 int nex[1000000 + 5];
10 
11 void get_next(int* p, int next[]) {
12     int pLen = len2;//要求循环节长度时这里才+1
13     next[0] = -1;
14     int k = -1;
15     int j = 0;
16     while (j < pLen - 1) {
17         if (k == -1 || p[j] == p[k]) {
18             ++j; ++k;
19             if (p[j] != p[k])
20                 next[j] = k;
21             else
22                 next[j] = next[k];
23         }
24         else {
25             k = next[k];
26         }
27     }
28 }
29 
30 int kmp(int* s, int* p) {
31     int i = 0;
32     int j = 0;
33     int sLen = len1;
34     int pLen = len2;
35     get_next(s2, nex);
36     while (i < sLen && j < pLen) {
37         //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
38         if (j == -1 || s[i] == p[j]) {
39             i++;
40             j++;
41         }
42         else {
43             //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
44             //next[j]即为j所对应的next值        
45             j = nex[j];
46         }
47     }
48     if (j == pLen)
49         return i - j;
50     else
51         return -1;
52 }
53 
54 int main() {
55     scanf("%d", &T);
56     while (T--) {
57         scanf("%d %d", &len1, &len2);
58         for (int i = 0; i < len1; i++)
59             scanf("%d", &s1[i]);
60         for (int i = 0; i < len2; i++)
61             scanf("%d", &s2[i]);
62         if (kmp(s1,s2) == -1)
63             printf("-1
");
64         else
65             printf("%d
", kmp(s1,s2)+1);
66     }
67     return 0;
68 }