KMP是字符串匹配的经典算法
也是众多字符串基础的重中之重
A.
题意：给T组数据，每组有长度为n和m的母串和模式串。判断模式串是否是母串的子串，如果是输出最先匹配完成的位置，否则输出-1.
做法：直接套用模板。把char改成int。kmp函数中在模式串遍历到结尾的时候return，若没遍历到结尾，也就是不是子串返回-1
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 int nexta[10005],a[1000005],s[10005];
7 int n,m;
8 void getnexta(int s[])
9 {
10 memset(nexta,0,sizeof(nexta));
11 int k = -1,j = 0;
12 nexta[0] = -1;
13
14 while(j < n )
15 {
16
17 if(k == -1 || s[k] == s[j])
18 {
19 nexta[j + 1] = k + 1;
20 j ++;
21 k ++;
22 }
23 else
24 {
25 k = nexta[k];
26 }
27 }
28
29 }
30 int kmp(int s[],int t[])//t模式串，s母串
31 {
32 getnexta(t);
33
34 int i = 0,j = 0;
35 while(i m)
36 {
37 if(j == -1 || s[i] == t[j])
38 {
39 i ++;
40 j ++;
41 }
42 else
43 {
44 j = nexta[j];
45 }
46 if(j == m)
47 {
48 return i - j+ 1;
49 }
50 }
51 return -1;
52 }
53 int main()
54 {
55 // freopen("in.txt","r",stdin);
56 int T;
57 scanf("%d",&T);
58 while(T--)
59 {
60 scanf("%d%d",&n,&m);
61 for(int i = 0;i )
62 {
63 scanf("%d",&a[i]);
64 }
65 for(int j = 0; j )
66 {
67 scanf("%d",&s[j]);
68 }
69 printf("%d\n",kmp(a,s));
70 }
71 return 0;
72 }
B.
题意：给T组数据，每组有两个字符串按顺序分别为模式串和母串。判断模式串在母串中出现的次数。模式串在母串中是可以相互覆盖的。
做法：直接套用模板。在kmp中当j==m也就是模式串完全匹配时，ans++，且j = nexta[j]
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 int nexta[1000006];
7 char t[1000006],s[1000006];
8 void getnexta(char s[])
9 {
10 memset(nexta,0,sizeof(nexta));
11 int n = strlen(s);
12 int k = -1,j = 0;
13 nexta[0] = -1;
14 while(j < n )
15 {
16
17 if(k == -1 || s[k] == s[j])
18 {
19 nexta[j + 1] = k + 1;
20 j ++;
21 k ++;
22 }
23 else
24 {
25 k = nexta[k];
26 }
27 }
28
29 }
30 int kmp(char s[],char t[])//t模式串，s母串.此种为返回首次匹配的位置，不能匹配则返回-1.
31 {
32 getnexta(t);
33 int ans = 0;
34 int n = strlen(s),m = strlen(t);
35 int i = 0,j = 0;
36 while(i m)
37 {
38 if(j == -1 || s[i] == t[j])
39 {
40 i ++;
41 j ++;
42 }
43 else
44 {
45 j = nexta[j];
46 }
47 if(j == m)//根据题目要求改变
48 {
49 ans ++;
50 j = nexta[j];
51 }
52 }
53 return ans;
54 }
55 int main()
56 {
57 // freopen("in.txt","r",stdin);
58 int T;
59 scanf("%d",&T);
60 while(T--)
61 {
62 scanf("%s%s",t,s);
63 printf("%d\n",kmp(s,t));
64 }
65 return 0;
66 }
C.
题意：输入母串和模式串，以’#‘为结束。剪纸花，从母串中减去模式串问能剪出多少。这就意味着求解模式串的数量时不能重叠覆盖
做法：模板。在kmp中当j==m也就是模式串完全匹配时，ans++，且j = 0.要再次从头开始匹配
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 int nexta[1006];
7 char t[1006],s[1006];
8 void getnexta(char s[])
9 {
10 memset(nexta,0,sizeof(nexta));
11 int n = strlen(s);
12 int k = -1,j = 0;
13 nexta[0] = -1;
14 while(j < n )
15 {
16
17 if(k == -1 || s[k] == s[j])
18 {
19 nexta[j + 1] = k + 1;
20 j ++;
21 k ++;
22 }
23 else
24 {
25 k = nexta[k];
26 }
27 }
28
29 }
30 int kmp(char s[],char t[])//t模式串，s母串.此种为返回首次匹配的位置，不能匹配则返回-1.
31 {
32 getnexta(t);
33 int ans = 0;
34 int n = strlen(s),m = strlen(t);
35 int i = 0,j = 0;
36 while(i m)
37 {
38 if(j == -1 || s[i] == t[j])
39 {
40 i ++;
41 j ++;
42 }
43 else
44 {
45 j = nexta[j];
46 }
47 if(j == m)//根据题目要求改变
48 {
49 ans ++;
50 j = 0;
51 }
52 }
53 return ans;
54 }
55 int main()
56 {
57 // freopen("in.txt","r",stdin);
58 while(1)
59 {
60 scanf("%s",s);
61 if(strcmp(s,"#") == 0)
62 break;
63 scanf("%s",t);
64 printf("%d\n",kmp(s,t));
65 }
66 return 0;
67 }
D.
题意：给T组数据，每组有一个字符串，只能在字符串的前面和后面增加字符，不能再中间增加，求要使这个字符串是周期循环的且周期的次数大于一，至少需要增加的字符数量。注意这个字符串是个手链，也就是说是增加字符后首位相连是周期的即可
做法：首先求最小循序节，考虑一种特殊情况就是nexta[n] = 0,这个时候前缀没有匹配后缀的地方，所以需要增加n个字符。求出最小循环节：n - nexta[n]。当n整除循环节时候，这时字符串已经是周期循环。当不整除时，最小循序节减去已经在字符串中的字符数目及ans = temp - (n % temp);（temp为最小循环节）
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 int nexta[100005];
7 char s[100005];
8 void getnexta(char s[])
9 {
10 memset(nexta,0,sizeof(nexta));
11 int n = strlen(s);
12 int k = -1,j = 0;
13 nexta[0] = -1;
14 while(j < n )
15 {
16 if(k == -1 || s[k] == s[j])
17 {
18 nexta[j + 1] = k + 1;
19 j ++;
20 k ++;
21 }
22 else
23 {
24 k = nexta[k];
25 }
26 }
27 }
28 int main()
29 {
30 // freopen("in.txt","r",stdin);
31 int T,ans,n,temp;
32 scanf("%d",&T);
33 while(T --)
34 {
35 scanf("%s",s);
36 n = strlen(s);
37 getnexta(s);
38 temp = n - nexta[n];//最小循环节
39 if(temp == n)
40 {
41 ans = n;
42 }
43 else if(n % temp == 0)
44 {
45 ans = 0;
46 }
47 else
48 {
49 ans = temp - (n % temp);
50 }
51 printf("%d\n",ans);
52 }
53 return 0;
54 }
E.
题意：给字符串的长度和一个字符串。读到eof。求每个字符串中在i之前的位置是循环的且次数大于1，求这个位置i以及循环的次数
做法：求每个位置i的最小循环节，判断是否整除和个数大于1，并用除法的值求次数
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 int nexta[1000002];
7 char s[1000002];
8 int n;
9 void getnexta()
10 {
11 memset(nexta,0,sizeof(nexta));
12 int k = -1,j = 0;
13 nexta[0] = -1;
14 while(j < n )
15 {
16
17 if(k == -1 || s[k] == s[j])
18 {
19 nexta[j + 1] = k + 1;
20 j ++;
21 k ++;
22 }
23 else
24 {
25 k = nexta[k];
26 }
27 }
28
29 }
30 int main()
31 {
32 // freopen("in.txt","r",stdin);
33 int t = 0,temp;
34 while(1)
35 {
36 t ++;
37 scanf("%d",&n);
38 if(n == 0)
39 break;
40 scanf("%s",s);
41 printf("Test case #%d\n",t);
42 getnexta();
43 for(int i = 1; i <= n; i ++)
44 {
45 //cout<46 //cout<
47 if(nexta[i] == 0)
48 {
49 continue;
50 }
51 else
52 {
53 temp = i - nexta[i] ;//循环小节的长度
54 if((i ) % temp == 0 && (i ) / temp > 1)//这是由于nexta[i]表示的是i-1
55 printf("%d %d\n",i ,(i ) / temp);
56 }
57
58 }
59 printf("\n");
60 }
61 return 0;
62 }
63
64 /*
65 a a b a a b a a b a a b
66 -1 0 1 0 1 2 3 4 5 6 7 8
67 0 1 2 3 4 5 6 7 8 9 10 11
68 */
F.
题意：每组给一个字符串，一直读到eof。这个字符串是重复写的AAAAAAA的一部分，求这个A最短是多少
做法：。。。。。。此题有问题，全网代码没有对的，我至少交了8+份代码
G.
题意：每组给以个字符串，一直读到‘.‘.字符串s = a^n，及都是由a构成的，求n的值
做法：求最小循环节，如果整除，那除得的数及为ans。如果不整除ans = 1
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 int nexta[1000002];
7 char s[1000002];
8 int n;
9 void getnexta()
10 {
11 memset(nexta,0,sizeof(nexta));
12 int k = -1,j = 0;
13 nexta[0] = -1;
14 while(j < n )
15 {
16
17 if(k == -1 || s[k] == s[j])
18 {
19 nexta[j + 1] = k + 1;
20 j ++;
21 k ++;
22 }
23 else
24 {
25 k = nexta[k];
26 }
27 }
28
29 }
30 int main()
31 {
32 //freopen("in.txt","r",stdin);
33 int ans;
34 while(1)
35 {
36 ans = 0;
37 scanf("%s",s);
38 if(strcmp(s,".") == 0)
39 break;
40 n = strlen(s);
41 getnexta();
42 if(n % (n - nexta[n]) == 0 )
43 ans = n / (n - nexta[n]);
44 else
45 ans = 1;
46 printf("%d\n",ans);
47 }
48 return 0;
49 }
50
51
52 //ababa
H.
题意：每组一个字符串，读到eof结束。寻找i使得字符串的前缀等于后缀
做法：首先n（字符串的长度）肯定是，因为此时前缀和后缀是一样的。对nexta[n]进行递归。及i= nexta[i].当nexta[i] == 0时结束。因为是nexta找到的所以以i为结束的字符串后缀等于以n为结束的字符串的后缀。可以看看kmp算法讲解中的图，体会一下
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 int nexta[1000002];
7 char s[1000002];
8 int ans[1000002];
9 int n;
10 void getnexta()
11 {
12 memset(nexta,0,sizeof(nexta));
13 int k = -1,j = 0;
14 nexta[0] = -1;
15 while(j < n )
16 {
17
18 if(k == -1 || s[k] == s[j])
19 {
20 nexta[j + 1] = k + 1;
21 j ++;
22 k ++;
23 }
24 else
25 {
26 k = nexta[k];
27 }
28 }
29
30 }
31
32 int main()
33 {
34 //freopen("in.txt","r",stdin);
35 int temp,k;
36 while(scanf("%s",s) != EOF)
37 {
38 k = 0;
39 if(strcmp(s,".") == 0)
40 break;
41 n = strlen(s);
42 getnexta();
43 temp = n;
44 ans[k] = n;
45 k ++;
46 while(nexta[temp]!= -0)
47 {
48 temp = nexta[temp];
49 ans[k] = temp;
50 k ++;
51 }
52 for(int i = k -1; i > 0; i --)
53 printf("%d ",ans[i]);
54 printf("%d\n",ans[0]);
55
56 }
57 return 0;
58 }
59
60
61 //ababa
I.
题意：T组数据，每组m个DNA序列，每个DNA序列都有60个字符，且只由ACGT几个字母构成。判断m个DNA序列最长公共的子串是什么？如果有相同长度的公共子串，则输出字典序最小的。如果小于3输出“no ……”，大于等于3输出字符串
做法：对第一个DNA序列取从i开始到结尾的子串。与其他DNA序列进行匹配。因为是从前向后匹配，在kmp时做出改变，求出每个DNA序列和子串匹配的最长长度，再对所有最长长度取最短的那个。注意对长度相等时的处理。其中还用到strncpy,可以复制一定长度的字符串到指定字符串中。注意在最后加‘\0‘
1 [cpp] view plain copy
2 //直接枚举第一串的所有后缀，然后与后面的所有串进行比较，判断有几个字母是相同的即可
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 int nexta[100];
9 char c[12][100];
10 char s[100];
11 int n,m,l;
12 void getnexta()
13 {
14 memset(nexta,0,sizeof(nexta));
15 int k = -1,j = 0;
16 nexta[0] = -1;
17 while(j < n )
18 {
19
20 if(k == -1 || s[k] == s[j])
21 {
22 nexta[j + 1] = k + 1;
23 j ++;
24 k ++;
25 }
26 else
27 {
28 k = nexta[k];
29 }
30 }
31
32 }
33 int kmp()
34 {
35 int k = 0,j = -1;
36 int maxx = 100,temp = 0;
37 for(int i = 1 ;i )
38 {
39 temp = 0;j = 0,k = 0;
40 while(j 60)
41 {
42 if(j == -1 || c[i][k] == s[j])
43 {
44 j ++;
45 k ++;
46
47 }
48
49 else
50 j = nexta[j];
51 if(j > temp)//每个DNA序列和子串匹配的最长长度
52 {
53 temp = j;
54 }
55
56 }
57 if(temp //所有DNA序列都和子串匹配的长度
58 maxx = temp;
59 }
60 return maxx;
61 }
62 int main()
63 {
64 //freopen("in.txt","r",stdin);
65 int T,temp,num;
66 n = 60;
67 scanf("%d",&T);
68 while(T--)
69 {
70 char result[100];
71 char t[100];
72 num = 0;
73 scanf("%d",&m);
74 for(int i = 0; i )
75 {
76 scanf("%s",&c[i]);
77 }
78 for(int i = 0; i <58; i ++)
79 {
80 l = 60 - i;
81 strcpy(s,c[0] + i);
82 getnexta();
83 temp = kmp();
84 if(num == temp)
85 {
86 strncpy(t,c[0] + i,temp);
87 if(t < result)
88 {
89 strcpy(result,t);
90 }
91 t[temp] = ‘\0‘;
92 }
93 else if(num < temp)
94 {
95 strncpy(result,c[0] + i,temp);
96 result[temp] = ‘\0‘;
97 num = temp;
98 }
99 }
100 //cout<
101 if(num >= 3)
102 {
103 printf("%s\n",result);
104 // cout<
105 }
106 else
107 printf("no significant commonalities\n");
108 }
109 return 0;
110 }
111
112
113 //ababa
J.
题意：每组给两个字符串以eof结尾。求s1的前缀，等于s2后缀的长度.如果长度不是零空格之后输出相同的部分，否则只输出零即可
做法：把s2接在s1后面，求nexta[n].注意求得的ans长度不能大于s1或s2
1 [cpp] view plain copy
2 /*考虑abcabcabcabc
3 abcabcabcabcabc这组数据也就是考虑当得数大于s1或s2时
4 */
5 #include
6 #include
7 #include
8 #include <string>
9 using namespace std;
10 int nexta[100002];
11 char s[100002];
12 char a[50002];
13 int n;
14 void getnexta()
15 {
16 memset(nexta,0,sizeof(nexta));
17 int k = -1,j = 0;
18 nexta[0] = -1;
19 while(j < n )
20 {
21
22 if(k == -1 || s[k] == s[j])
23 {
24 nexta[j + 1] = k + 1;
25 j ++;
26 k ++;
27 }
28 else
29 {
30 k = nexta[k];
31 }
32 }
33
34 }
35 int main()
36 {
37 // freopen("in.txt","r",stdin);
38 while(scanf("%s%s",s,a) != EOF)
39 {
40 int ans = 0;
41 strcat(s,a);
42 int m = strlen(a);
43 n = strlen(s);
44 getnexta();
45 //cout<46 //cout<47 // cout<
48 ans = nexta[n];
49 //cout<
50 if(ans != 0)
51 {
52 if(ans > n || ans > m)
53 ans = min(n - m,m);
54 for(int i = 0; i )
55 printf("%c",s[i]);
56 printf(" %d\n",ans);
57
58 }
59 else
60 printf("0\n");
61 }
62 return 0;
63 }
K
题意：给T组数据，每组数据给一个长度为n的字符串s。求字符串每个前缀出现的次数，结果mod 10007
做法：dp[i]表示的是长度为i的字符串的前缀的个数。dp[i] = dp[nexta[i]] + 1。以i-1为结尾的后缀的个数是next[i],也是前缀的长度。这个前缀的长度中字符串本身的前缀出现的次数。因为以i - 1为后缀的字符串中都又出现了一次
ababa
dp[1] = 1 a
dp[2] = 1 ab
dp[3] = 2 aba a
dp[4] = 2 abab ab
dp[5] = 3 ababa aba a
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 #include
6 #include
L.
题意：给T组数据，每组数据第一行是26个字母表示[a,z]所对应的密文字母。第二行的字符串由两部分组成，第一部分是密文部分，第二部分是明文部分。明文部分可能是不完整的，也可能是完整的输出完整的明文部分
做法：先输出第二行的全部字符串。然后对整个字符串进行变化，把密文部分转化为明文部分。原串密文部分的长度一定大于等于明文部分。明文部分最长就是从整个字符串的一半开始的。将转化后的字符串与未转化之前的字符串的后半部分进行匹配。匹配到的返回结果就是原字符串中明文的个数：temp。则密文的个数为n - temp.实际应该的长度为2 * n - 2 * temp.应该输出的长度为：2 * n - 2 * temp - n.从转换后的字符串的temp位开始直接输出即可。从该位置开始到字符串的长度减去该位置都是待输出的不完整的字符串。其实质就是用完整的明文串，与题目中给出的不一定完整的明文串进行匹配。注意其中完整的是模式串，不完整的是所谓的母串。模式串是从头开始匹配的。而母串不是
提一下如何将密文转化为明文，将第一行该位置对应的字母转化为该位置i转化为字母（i + ‘a‘)
ps：这也就意味着，不要从头开始匹配，是母串。而普通kmp的模式串一定要是从头开始匹配的。
abcdefghijklmnopqrstuvwxyz
abcdab
abcdab
1 [cpp] view plain copy
2 //密文和明文前后两端是重复的
3 #include
4 #include
5 #include
6 #include
7 #include
Q.
题意：每组n个字符串，以eof结束。求每个字符串中满足S[i]=S[i+P] for i in [0..SIZE(S)-p-1],的位置。
做法：其实还是前缀与后缀相等，其中p是后缀开始的地方。递归nexta即可。因为nexta递归得到的以i为结束后缀等于前缀，等于整个长度的后缀.注意p的大小是n - nexta[n](nexta[n]是后缀的长度，n - nexta[n]就是后缀开始的位置了）
1 #include
2 #include
3 #include
4 using namespace std;
5 int nexta[1000005];
6 char s[1000005];
7 int ans[1000005];
8 int n;
9 void getnexta()
10 {
11 int j = 0,k = -1;
12 nexta[0] = -1;
13 while(j < n)
14 {
15 if(k == -1 || s[j] == s[k])
16 {
17 nexta[j + 1] = k + 1;
18 j ++;
19 k ++;
20 }
21 else
22 {
23 k = nexta[k];
24 }
25 }
26 }
27 int main()
28 {
29 // freopen("in.txt","r",stdin);
30 int T;
31 scanf("%d",&T);
32 for(int t=1; t<= T; t++)
33 {
34 scanf("%s",s);
35 n = strlen(s);
36 getnexta();
37 int a = n;
38 int num = 0;
39 while(nexta[a] != -1)
40 {
41 ans[num] = n - nexta[a];
42 num ++;
43 a = nexta[a];
44 }
45 printf("Case #%d: %d\n",t,num);
46 for(int i = 0; i 1; i ++)
47 {
48 printf("%d ",ans[i]);
49 }
50 printf("%d\n",ans[num - 1]);
51 }
52 return 0;
53 }
Z.
题意：n个字符串，每个字符串都可以写成EAEBE的形式，其中E可以为空，寻找最长的E
做法：首先我们很容易知道E最长长度为nexta[n]，然后判断中间的那个E是否存在，设E的长度为i。从开头位置加1开始遍历（i+1)，到<（n - i)为止，如果有next[j] == i那么可以判断这个长度的E存在。从E可能的最大长度开始遍历
1 [cpp] view plain copy
2 #include
3 #include
4 #include
5 using namespace std;
6 char s[1000005];
7 char t[1000005];
8 int nexta[1000005];
9 int n;
10 void getnexta()
11 {
12 memset(nexta,0,sizeof(nexta));
13 nexta[0] = -1;
14 int k = -1,j = 0;
15 while(j < n)
16 {
17 if(k == -1 || s[k] == s[j])
18 {
19 nexta[j + 1] = k + 1;
20 j ++;
21 k ++;
22 }
23 else
24 k = nexta[k];
25 }
26 }
27
28 int main()
29 {
30 // freopen("in.txt","r",stdin);
31 int T;
32 scanf("%d",&T);
33 while(T--)
34 {
35 scanf("%s",s);
36 n = strlen(s);
37 getnexta();
38 //cout<
39 int ans = 0,i;
40 bool flag ;
41 for(i = min(n / 3 - 1,nexta[n] - 1);i >= 0;i --)
42 {
43 //cout<
44 for(int j = i + 1; j )
45 {
46 flag = false;
47 if(nexta[j] == i )
48 {
49 ans = i + 1;
50 flag = true;
51 break;
52 }
53 }
54 if(flag)
55 break;
56 }
57 if(i == -1)
58 ans = 0;
59 cout<endl;
60 }
61 return 0;
62 }
使用高级算法会减少思维难度，相比较来说，高级算法虽然难度大，但是实用性更强
KMP算法应用举例
京公网安备 11010802041100号