KMP专题

1、HDU 1711 Number Sequence

　　题意：给出两个数字串a,b,问能否使得数字串b为a的子串，能则输出最小的匹配位置。

　　思路：KMP模板题

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1000010;
 5 const int maxm = 10010;
 6 int p[maxm];
 7 int des[maxn];
 8 int Next[maxm];
 9 int n, m;
10 void GetNext(int *next, int *src, int len)
11 {//next和src都从下标1开始存储
12     next[1] = 0;
13     int j = 1, i = 0;
14     while (j <= len)
15     {
16         if (i == 0 || src[j] == src[i])
17         {
18             j++;
19             i++;
20             next[j] = i;
21         }
22         else i = next[i];
23     }
24 }
25 
26 int KMP(int *T, int *P, int *next)//在目标串T中从位置1开始查找模式串P第一次出现的位置
27 {
28     int lenT = n;
29     int lenP = m;
30     int posT = 1, posP = 1;
31     while (posP <= lenP&&posT <= lenT)
32     {
33         if (posP == 0 || T[posT] == P[posP])
34         {
35             ++posT;
36             ++posP;
37         }
38         else posP = next[posP];
39     }
40     if (posP <= lenP) return -1;
41     else return posT - lenP;
42 }
43 int main()
44 {
45     int t;
46     scanf("%d", &t);
47 
48     while (t--)
49     {
50         scanf("%d%d", &n, &m);
51         for (int i = 1; i <= n; i++) scanf("%d", &des[i]);
52         for (int i = 1; i <= m; i++) scanf("%d", &p[i]);
53         GetNext(Next, p, m);
54         printf("%d
", KMP(des, p, Next));
55     }
56     return 0;
57 }

View Code

2、HDU 1686 Oulipo

　　题意：给出模式串p,文本串t,求p在t中出现的次数(可重叠)

　　思路：KMP同时记录匹配的个数。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1000100;
 5 const int maxp = 10010;
 6 char t[maxn];
 7 char p[maxp];
 8 int Next[maxp];
 9 void GetNext(int *next, char *src, int len)
10 {//next和src都从下标0开始存储
11     next[0] = -1;
12     int j = 0, i = -1;
13     while (j < len)
14     {
15         if (i == -1 || src[j] == src[i])
16         {
17             j++;
18             i++;
19             next[j] = i;
20         }
21         else i = next[i];
22     }
23 }
24 
25 int KMP(char*T, char *P, int *next)//在目标串T中从位置1开始查找模式串P第一次出现的位置
26 {
27     int lenT = strlen(T);
28     int lenP = strlen(P);
29     int posT = 0, posP = 0;
30     int cnt = 0;
31     while (posT <lenT)
32     {
33         if (posP == -1 || T[posT] == P[posP])
34         {
35             ++posT;
36             ++posP;
37         }
38         else posP = next[posP];
39         if (posP== lenP)
40         {
41             cnt++;
42             posP = next[posP];
43         }
44     }
45     return cnt;
46 }
47 int main()
48 {
49     int Case;
50     scanf("%d", &Case);
51     while (Case--)
52     {
53         scanf("%s", p);
54         scanf("%s", t);
55         GetNext(Next, p, strlen(p));
56         printf("%d
", KMP(t,p, Next));
57     }
58     return 0;
59 }

View Code

3、hdu 2087 剪花布条

　　题意：给出a串和b串,求b串在a串中出现的次数(不可重叠)

　　思路：KMP。注意更新指针时和上一题的不同。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1010;
 5 const int maxp = 1010;
 6 char t[maxn];
 7 char p[maxp];
 8 int Next[maxp];
 9 void GetNext(int *next, char *src, int len)
10 {//next和src都从下标0开始存储
11     next[0] = -1;
12     int j = 0, i = -1;
13     while (j < len)
14     {
15         if (i == -1 || src[j] == src[i])
16         {
17             j++;
18             i++;
19             next[j] = i;
20         }
21         else i = next[i];
22     }
23 }
24 
25 int KMP(char*T, char *P, int *next)//在目标串T中从位置1开始查找模式串P第一次出现的位置
26 {
27     int lenT = strlen(T);
28     int lenP = strlen(P);
29     int posT = 0, posP = 0;
30     int cnt = 0;
31     while (posT <lenT)
32     {
33         if (posP == -1 || T[posT] == P[posP])
34         {
35             ++posT;
36             ++posP;
37         }
38         else posP = next[posP];
39         if (posP == lenP)
40         {
41             cnt++;
42             posP++;
43         }
44     }
45     return cnt;
46 }
47 int main()
48 {
49     while (~scanf("%s",&t))
50     {
51         if (t[0] == '#')break;
52         scanf("%s", p);
53         GetNext(Next, p, strlen(p));
54         printf("%d
", KMP(t, p, Next));
55     }
56     return 0;
57 }

View Code

4、HDU 3746 Cyclic Nacklace

　　题意：求最少在结尾补几个字符才能使得此串形成循环.

　　思路：lenB%(lenB-Next[lenB])==0则其有周期lenB/(lenB-Next[lenB])，其中最小循环节长度是lenB-Next[lenB]。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 100010;
 5 const int maxp = 100010;
 6 char t[maxn];
 7 char p[maxp];
 8 int Next[maxp];
 9 void GetNext(int *next, char *src, int len)
10 {//next和src都从下标0开始存储
11     next[0] = -1;
12     int j = 0, i = -1;
13     while (j < len)
14     {
15         if (i == -1 || src[j] == src[i])
16         {
17             j++;
18             i++;
19             next[j] = i;
20         }
21         else i = next[i];
22     }
23 }
24 int main()
25 {
26     int C;
27     scanf("%d", &C);
28     while (C--)
29     {
30         scanf("%s", &t);
31         int ll = strlen(t);
32         GetNext(Next, t,ll);
33         int len = ll - Next[ll];//循环节长度
34         if (len != ll&&ll%len == 0) printf("0
");
35         else printf("%d
", len - Next[ll] % len);
36     }
37     return 0;
38 }

View Code

5、POJ 1961 Period

　　题意：求出母串的所有前缀的循环节大于1的循环串。

　　思路：根据next数组的性质即 i-next[i] 为一个循环节的长度。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1000010;
 5 char des[maxn];
 6 int Next[maxn];
 7 int n, Case;
 8 void GetNext(int *next, char *src, int len)
 9 {
10     next[0] = -1;
11     int j = 0, i = -1;
12     while (j <len)
13     {
14         if (i == -1 || src[j] == src[i])
15         {
16             j++;
17             i++;
18             next[j] = i;
19         }
20         else i = next[i];
21     }
22 }
23 void Solve()
24 {
25     printf("Test case #%d
", Case++);
26     for (int i = 1; i <= n; i++)
27     {
28         int len = i - Next[i];
29         if (i!= len && i % len == 0)
30         {
31             printf("%d %d
", i, i / len);
32         }
33     }
34     printf("
");
35 }
36 int main()
37 {
38     Case = 1;
39     while (~scanf("%d", &n) && n)
40     {
41         scanf("%s", des);
42         GetNext(Next, des, n);
43         Solve();
44     }
45     return 0;
46 }

View Code

6、HUST 1010 The Minimum Length

　　题意：有一个字符串A，一次次的重写A，会得到一个新的字符串AAAAAAAA.....,现在将这个字符串从中切去一部分得到一个字符串B，例如有一个字符串A="abcdefg".，复制几次之后得到abcdefgabcdefgabcdefgabcdefg....，现在切取一部分，得到字符串B，现在只给出字符串B，求出字符串A的长度。

　　思路：最小的循环节：len-next[len]。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1000100;
 5 char des[maxn];
 6 int Next[maxn];
 7 int n, Case;
 8 void GetNext(int *next, char *src, int len)
 9 {
10     next[0] = -1;
11     int j = 0, i = -1;
12     while (j <len)
13     {
14         if (i == -1 || src[j] == src[i])
15         {
16             j++;
17             i++;
18             next[j] = i;
19         }
20         else i = next[i];
21     }
22 }
23 void Solve()
24 {
25     printf("%d
",n-Next[n]);
26 }
27 int main()
28 {
29     while (~scanf("%s",des))
30     {
31         n = strlen(des);
32         GetNext(Next, des, n);
33         Solve();
34     }
35     return 0;
36 }

View Code

7、poj 2406 Power Strings

　　题意：给一个字符串a，它可以看成若干个相同的子串循环形成的，求最大循环次数n。

　　思路：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 1000100;
 5 char des[maxn];
 6 int Next[maxn];
 7 int n, Case;
 8 void GetNext(int *next, char *src, int len)
 9 {
10     next[0] = -1;
11     int j = 0, i = -1;
12     while (j <len)
13     {
14         if (i == -1 || src[j] == src[i])
15         {
16             j++;
17             i++;
18             next[j] = i;
19         }
20         else i = next[i];
21     }
22 }
23 void Solve()
24 {
25     if(n%(n-Next[n])==0)printf("%d
", n/(n - Next[n]));
26     else printf("1
");
27 }
28 int main()
29 {
30     while (~scanf("%s", des))
31     {
32         if (des[0] == '.')break;
33         n = strlen(des);
34         GetNext(Next, des, n);
35         Solve();
36     }
37     return 0;
38 }

View Code

8、poj 2752 Seek the Name, Seek the Fame

　　题意：给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。从小到大依次输出这些子串的长度。

　　思路：next[i]的意义就是：前面长度为i的字串的【前缀和后缀的最大匹配长度】。所以对于这道题，求出len处的next值，并递归的向下求出所有的next值，得到的就是答案。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 400100;
 5 char des[maxn];
 6 int Next[maxn];
 7 int n, Case;
 8 void GetNext(int *next, char *src, int len)
 9 {
10     next[0] = -1;
11     int j = 0, i = -1;
12     while (j <len)
13     {
14         if (i == -1 || src[j] == src[i])
15         {
16             j++;
17             i++;
18             next[j] = i;
19         }
20         else i = next[i];
21     }
22 }
23 void Solve(int x)
24 {
25     if (x != 0)
26     {
27         Solve(Next[x]);
28         if (x == n) printf("%d
", x);
29         else printf("%d ", x);
30     }
31 }
32 int main()
33 {
34     while (~scanf("%s", des))
35     {
36         n = strlen(des);
37         GetNext(Next, des, n);
38         Solve(n);
39     }
40     return 0;
41 }

View Code

9、POJ 3080 Blue Jeans

　　题意：找出n个串中最长的公共串，并且要求字典序最大。

　　思路：直接枚举第一串的所有子串，然后与后面的所有串进行比较即可。

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 const int N = 107;
 7 char s[N][61];
 8 int Next[N];
 9 
10 void GetNext(char a[], int n)
11 {
12     int i = 0, j = -1;
13     Next[0] = -1;
14     while (i<n)
15     {
16         if (j == -1 || a[i] == a[j])
17             Next[++i] = ++j;
18         else
19             j = Next[j];
20     }
21 }
22 
23 int kmp(char a[], char b[], int n)
24 {
25     int i = 0, j = 0;
26     while (i<60)
27     {
28 
29         if (j == -1 || b[i] == a[j])
30             i++, j++;
31         else
32             j = Next[j];
33         if (j == n)
34             return true;
35     }
36     return false;
37 }
38 
39 int main()
40 {
41     int T, n, f;
42     scanf("%d", &T);
43     while (T--)
44     {
45         char ans[N] = "Z";
46         scanf("%d", &n);
47         for (int i = 0; i<n; i++)
48             scanf("%s", s[i]);
49         for (int len = 60; len >= 3; len--)//子串的长度
50         {
51             for (int i = 0; i <= 60 - len; i++)//子串的开始下标
52             {
53                 char subStr[N] = { 0 };
54                 strncpy(subStr, s[0] + i, len);
55 
56                 GetNext(subStr, len);//从subStr中得到Next
57                 int flag = 0;
58                 for (int j = 1; j<n; j++)
59                 {
60                     if (!kmp(subStr, s[j], len))
61                     {
62                         flag = 1;
63                         break;
64                     }
65                 }
66                 if (flag == 0 && strcmp(ans, subStr)>0)
67                     strcpy(ans, subStr);
68             }
69             f = 0;
70             if (ans[0] != 'Z')
71             {
72                 printf("%s
", ans);
73                 f = 1;
74                 break;
75             }
76         }
77         if (f == 0)
78             printf("no significant commonalities
");
79 
80     }
81     return 0;
82 }

View Code

10、HDU 2594 Simpsons’ Hidden Talents

　　题意：给定两个字符串s1,s2,求最长的s1前缀ss使得ss为s2的后缀,输出该字符串和其长度。

　　思路：①将s1和s2拼接在一起，next[len]也就是最终答案，不过需要注意的是next[len]不能大于s1,s2的长度。

　　　　 ②题目要求最长的s1的前缀同时满足是s2的后缀，可以反过来想一下，把s2作为主串，s1为子串,然后s1不断往后移动，匹配之后就可以了.

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxn = 50010*2;
 5 const int maxp = 50010*2;
 6 char t[maxn];
 7 char p[maxp];
 8 int Next[maxp];
 9 void GetNext(int *next, char *src, int len)
10 {//next和src都从下标0开始存储
11     next[0] = -1;
12     int j = 0, i = -1;
13     while (j < len)
14     {
15         if (i == -1 || src[j] == src[i])
16         {
17             j++;
18             i++;
19             next[j] = i;
20         }
21         else i = next[i];
22     }
23 }
24 
25 int KMP(char*T, char *P, int *next)//在目标串T中从位置1开始查找模式串P第一次出现的位置
26 {
27     int lenT = strlen(T);
28     int lenP = strlen(P);
29     int posT = 0, posP = 0;
30     while (posT <lenT)
31     {
32         if (posP == -1 || T[posT] == P[posP])
33         {
34             ++posT;
35             ++posP;
36         }
37         else posP = next[posP];
38     }
39     return posP;
40 }
41 int main()
42 {
43     while (~scanf("%s", &p))
44     {
45         scanf("%s", t);
46         int lt = strlen(t), lp = strlen(p);
47         strcat(p, t);//新增
48         GetNext(Next, p, strlen(p));
49         //int ll=KMP(t, p, Next);
50         int ll = lt+lp;
51         while (Next[ll] > lt || Next[ll] > lp) ll = Next[ll];
52         ll = Next[ll];
53         if (ll>0)
54         {
55             for (int i = 0; i < ll; i++) printf("%c", p[i]);
56             printf(" %d
", ll);
57         }
58         else printf("0
");
59     }
60     return 0;
61 }

View Code

11、hdu 3336 Count the string

　　题意：给出s,求所有s的前缀在s中出现的次数的和。

　　思路：因为next[i]表示前i个字符所组成的字符串的最大前后缀匹配长度

　　　　①不断递归求得next[i]，cnt++.

　　　　②所求=字串的前缀个数+与前缀相同的子串。不断累加next[i](当next[i]!=0&&next[i+1]!=next[i])

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxp = 200010;
 5 const int MOD = 10007;
 6 char p[maxp];
 7 int Next[maxp];//next数组的值就是当前子串的后缀与前缀匹配的个数
 8 void GetNext(int *next, char *src, int len)
 9 {//next和src都从下标0开始存储
10     next[0] = -1;
11     int j = 0, i = -1;
12     while (j < len)
13     {
14         if (i == -1 || src[j] == src[i])
15         {
16             j++;
17             i++;
18             next[j] = i;
19         }
20         else i = next[i];
21     }
22 }
23 
24 int main()
25 {
26     int t;
27     scanf("%d", &t);
28     while (t--)
29     {
30         int lp;
31         scanf("%d", &lp);
32         scanf("%s", p);
33         GetNext(Next, p, lp);
34         int ans = lp%MOD;
35         for (int i = 1; i <= lp; i++)
36         {
37             int tmp = i;
38             while (Next[tmp]) ans = (ans + 1) % MOD, tmp = Next[tmp];
39         }
40         printf("%d
", ans);
41     }
42     return 0;
43 }

View Code

12、HDU 4300 Clairewds message

　　题意：给你一个加密协议，即26个英文字母加密对应表，然后给你一个前一段是加密串，后一段为加密串对应的原串的字符串（原串可能小于加密串）输出最短的原串和加密串。

　　思路：先将原串S全部反加密得到串S'，再将S'串去匹配S，得到明文的长度。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <cstdlib>
 5 #include <iostream>
 6 #include <algorithm>
 7 using namespace std;
 8 const int MAXN = 100017;
 9 
10 char strm[MAXN];//密码表
11 char strz[MAXN];//不完整的密文和密文
12 char str[MAXN]; //密码表转换后
13 char s[MAXN];   //密文和明文转换后
14 int Next[MAXN];
15 
16 void getnext(char T[], int len)
17 {
18     int i = 0, j = -1;
19     Next[0] = -1;
20     while (i < len)
21     {
22         if (j == -1 || T[i] == T[j])
23         {
24             i++, j++;
25             Next[i] = j;
26         }
27         else
28             j = Next[j];
29     }
30 }
31 int KMP(int len1, int len2)
32 {
33     int i, j = 0;
34     if (len1 % 2 == 1)
35     {
36         i = len1 / 2 + 1;
37     }
38     else
39         i = len1 / 2;
40     while (i < len1 && j < len2)
41     {
42         if (j == -1 || strz[i] == s[j])
43         {
44             i++, j++;
45         }
46         else
47             j = Next[j];
48     }
49     return j;//j值代表的就是前缀和后缀的最长相等长度
50 }
51 
52 int main()
53 {
54     int t;
55     scanf("%d", &t);
56     while (t--)
57     {
58         scanf("%s", strm);
59         for (int i = 0; i < 26; i++)
60         {
61             char ss = strm[i];
62             str[ss] = i;
63         }
64         scanf("%s", strz);
65         int lenz = strlen(strz);
66         for (int i = 0; i < lenz; i++)//将密文和明文按照密码表转换
67         {
68             int tt = str[strz[i]];
69             s[i] = 'a' + tt;
70         }
71         int lens = strlen(s);
72         getnext(s, lens);
73         int j = KMP(lenz, lens);//得到密文的个数
74         if (j * 2 == lenz)//前缀和后缀恰各占一半
75         {
76             printf("%s
", strz);
77         }
78         else
79         {
80             int tt = lenz - j;
81             printf("%s", strz);
82             for (int i = j; i < tt; i++)//需要添加的明文
83             {
84                 printf("%c", s[i]);
85             }
86             printf("
");
87         }
88     }
89     return 0;
90 }

View Code

13、POJ 3450 Corporate Identity

　　题意：求n个字符串的最长公共字串。

　　思路：选取其中一个字符串，枚举其所有后缀，KMP求得其后缀和其余字符串的最长前缀的最小值，更新ans.

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<string.h>
 5 using namespace std;
 6 const int maxn = 4010;
 7 const int maxl = 210;
 8 char str[maxn][maxl];
 9 int Next[maxl];
10 char tstr1[maxl], tstr2[maxl];
11 int n;
12 void GetNext(int *next, char *src, int len)
13 {//next和src都从下标0开始存储
14     next[0] = -1;
15     int j = 0, i = -1;
16     while (j < len)
17     {
18         if (i == -1 || src[j] == src[i])
19         {
20             j++;
21             i++;
22             next[j] = i;
23         }
24         else i = next[i];
25     }
26 }
27 
28 int KMP(char*T, char *P, int *next)
29 {//查找字符串P在字符串T的最长前缀子字符串
30     int lenT = strlen(T);
31     int lenP = strlen(P);
32     int posT = 0, posP = 0;
33     int cnt = 0;
34     int maxmatch = 0;
35     while (posP<lenP&&posT <lenT)
36     {
37         if (posP == -1 || T[posT] == P[posP])
38         {
39             ++posT;
40             ++posP;
41             maxmatch = max(maxmatch, posP);
42         }
43         else posP = next[posP];
44     }
45     return maxmatch;
46 }
47 int main()
48 {
49     while (~scanf("%d", &n) && n)
50     {
51         for (int i = 1; i <= n; i++) scanf("%s", str[i]);
52         int len = strlen(str[1]);
53         int ans = 0, pos = 0;
54         for (int i = 0; i < len; i++)
55         {//遍历第一个字符串的所有后缀p
56             GetNext(Next, str[1] + i, len - i);
57             int tl = maxl;
58             for (int j = 2; j <= n; j++)
59             {//得到后缀p和剩余n-1个字符串的相同前缀的最小值
60                 tl = min(tl, KMP(str[j], str[1] + i, Next));
61             }
62             if (tl > ans) ans = tl, pos = i;
63             else if (tl == ans)
64             {//得到字典序较小的
65                 memset(tstr1, 0, sizeof(tstr1));
66                 memset(tstr2, 0, sizeof(tstr2));
67 
68                 strncpy(tstr1, str[1] + pos, ans);
69                 strncpy(tstr2, str[1]+i,ans);
70                 if (strcmp(tstr2, tstr1) < 0) pos = i;
71             }
72         }
73         if (ans > 0)
74         {
75             memset(tstr1, 0, sizeof(tstr1));
76             strncpy(tstr1, str[1] + pos, ans);
77             printf("%s
", tstr1);
78         }
79         else printf("IDENTITY LOST
");
80     }
81     return 0;
82 }
83 /*
84 4
85 abcd
86 abcd
87 abcd
88 abcd
89 3
90 abc
91 abcc
92 ab
93 
94 */

View Code

14、HDU 1238 Substrings

　　题意：找到一个子串，该子串的顺或逆为所有字符串的子串，求其最长长度。

　　思路：枚举子串，和其他字符串匹配。

  1 #include<iostream>  
  2 #include<cstdio>  
  3 #include<cstring>  
  4 #include<cstdlib>  
  5 #include<algorithm>  
  6 using namespace std;
  7 const int inf = 0x3f3f3f3f;
  8 const int mod = 1000000007;
  9 const int maxn = 500005;
 10 typedef long long ll;
 11 void get_next(char *s, int *Next)
 12 {
 13     int len = strlen(s);
 14     Next[0] = -1;
 15     int index;
 16     for (int i = 1; i<len; ++i)
 17     {
 18         index = Next[i - 1];
 19         while (index >= 0 && s[i] != s[index + 1])
 20         {
 21             index = Next[index];
 22         }
 23         if (s[i] == s[index + 1])
 24         {
 25             Next[i] = index + 1;
 26         }
 27         else
 28         {
 29             Next[i] = -1;
 30         }
 31     }
 32 }
 33 int KMP(char *target, char *pattern)
 34 {
 35     int len1 = strlen(target);
 36     int len2 = strlen(pattern);
 37     int Next[maxn];
 38     get_next(pattern, Next);
 39     int i = 0, j = 0;
 40     while (i < len1 && j < len2)
 41     {
 42         if (target[i] == pattern[j])
 43         {
 44             ++i;
 45             ++j;
 46         }
 47         else if (j == 0)
 48         {
 49             ++i;
 50         }
 51         else
 52         {
 53             j = Next[j - 1] + 1;
 54         }
 55     }
 56     if (j == len2)
 57     {
 58         return i - j;
 59     }
 60     else
 61     {
 62         return -1;
 63     }
 64 }
 65 char str[101][101];
 66 int main()
 67 {
 68     int n, t, k;
 69     char s1[101], s2[101];
 70     scanf("%d", &t);
 71     while (t--)
 72     {
 73         scanf("%d", &n);
 74         int pos = 0, MIN = inf;
 75         int flag = 0;
 76         for (int i = 0; i<n; ++i)
 77         {
 78             scanf("%s", str[i]);
 79             int len = strlen(str[i]);
 80             if (len < MIN)
 81             {
 82                 MIN = len;
 83                 pos = i;
 84             }
 85         }
 86         for (int i = MIN; i>0; --i)
 87         {//枚举子串长度，从大开始  
 88             for (int j = 0; j + i <= MIN; ++j)
 89             {//枚举子串起点  
 90                 for (k = 0; k<i; ++k)
 91                 {//生成子串和反串  
 92                     s1[k] = str[pos][k + j];
 93                     s2[i - k - 1] = str[pos][k + j];
 94                 }
 95                 s1[i] = 0;
 96                 s2[i] = 0;
 97                 for (k = 0; k<n; ++k)
 98                 {//匹配  
 99                     if (KMP(str[k], s1) == -1 && KMP(str[k], s2) == -1)
100                     {
101                         break;
102                     }
103                 }
104                 if (k == n)
105                 {
106                     flag = 1;
107                     printf("%d
", i);
108                     break;
109                 }
110             }
111             if (flag)break;
112         }
113         if (!flag)
114         {
115             printf("0
");
116         }
117     }
118     return 0;
119 }

View Code

15、HDU 3374 String Problem

　　题意：求给出字符串的最小和最大表示的开始位置，并且确定其数目。

　　思路：字符串最小最大表示模板。数目可通过最小循环节len-Next[len]确定。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 #define MAXN 1000100
 8 
 9 int len;
10 int Next[MAXN];
11 char Str[MAXN];
12 int minTimes, maxTimes;
13 int minRank, maxRank;
14 
15 //求最小表示的起始坐标
16 int getMin()
17 {
18     int i = 0, j = 1, k = 0;
19     while (i< len && j< len&&k<len)
20     {
21         if (Str[(i + k)%len] == Str[(j + k)%len])
22             k++;
23         else
24         {
25             if (Str[(i + k) % len] > Str[(j + k) % len])
26                 i +=k + 1;
27             else
28                 j +=k+1;
29             k = 0;
30             if (i == j)//若滑动后i == j那么j++
31                 j++;
32         }
33     }
34     return min(i, j);
35 }
36 
37 //求最大表示的起始坐标
38 int getMax()
39 {
40     int i = 0, j = 1, k = 0;
41     while (i< len && j< len&&k<len)
42     {
43         if (Str[(i + k)%len] == Str[(j + k)%len])
44             k++;
45         else
46         {
47             if (Str[(i + k) % len] < Str[(j + k) % len])
48                 i = i + k + 1;
49             else
50                 j = j + k + 1;
51             k = 0;
52             if (i == j)//若滑动后i == j那么j++
53                 j++;
54         }
55     }
56     return min(i, j);
57 }
58 //求next数组
59 void GetNext(int *next, char *src, int len)
60 {//next和src都从下标0开始存储
61     next[0] = -1;
62     int j = 0, i = -1;
63     while (j < len)
64     {
65         if (i == -1 || src[j] == src[i])
66         {
67             j++;
68             i++;
69             next[j] = i;
70         }
71         else i = next[i];
72     }
73 }
74 int main()
75 {
76     while (~scanf("%s", Str))
77     {
78 
79         int flag;
80         len = strlen(Str);
81         //求字符串的最小表示
82         minRank = getMin();
83         //求字符串的最大表示
84         maxRank = getMax();
85         GetNext(Next,Str,len);
86         minTimes = maxTimes = (len % (len - Next[len]) ? 1 : len / (len - Next[len]));
87         //输出
88         printf("%d %d %d %d
", minRank + 1, minTimes, maxRank + 1, maxTimes);
89     }
90     return 0;
91 }

View Code

16、hdu 2609 How many

　　题意：求给出的n的字符串的不同数目。（如果一个字符串通过旋转能够得到另一个字符串，则当成相同字符串）

　　思路：将所有字符串用最小表示法表示，然后set一下。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string.h>
 4 #include<string>
 5 #include<set>
 6 using namespace std;
 7 const int maxn = 10010;
 8 const int maxl = 110;
 9 char s[maxl];
10 char tmp[maxl];
11 set<string>ss;
12 int n;
13 //求最小表示的起始坐标
14 int getMin(char *Str,int len)
15 {
16     int i = 0, j = 1, k = 0;
17     while (i< len && j< len&&k<len)
18     {
19         if (Str[(i + k) % len] == Str[(j + k) % len])
20             k++;
21         else
22         {
23             if (Str[(i + k) % len] > Str[(j + k) % len])
24                 i += k + 1;
25             else
26                 j += k + 1;
27             k = 0;
28             if (i == j)//若滑动后i == j那么j++
29                 j++;
30         }
31     }
32     return min(i, j);
33 }
34 int Solve()
35 {
36     ss.clear();
37     for (int i = 1; i <= n; i++)
38     {
39         scanf("%s", s);
40         int len = strlen(s);
41         int pos = getMin(s, len);
42         memset(tmp, 0, sizeof(tmp));
43         strncpy(tmp, s+pos, len - pos);
44         strncat(tmp, s, pos);
45         ss.insert(string(tmp));
46     }
47     return ss.size();
48 }
49 int main()
50 {
51     while (~scanf("%d", &n))
52     {
53         printf("%d
", Solve());
54     }
55     return 0;
56 }

View Code

17、FZU Problem 1901 Period II

　　题意：给你一个字符串str，对于每个str长度为p的前缀，如果str[i]==str[p+i](p+i<len)，那么我们认为它是一个periodic prefixs.求所有满足题意的前缀的长度p。

　　思路：对于模式串str，next数组的意义就是：如果next(j)=t,那么str[1…t]=str[len-t+1…len]。所以不断递归打印next[j]即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn = 1000010;
 5 char des[maxn];
 6 int Next[maxn];
 7 int ans[maxn];
 8 void GetNext(int *next, char *src, int len)
 9 {//next和src都从下标0开始存储
10     next[0] = -1;
11     int j = 0, i = -1;
12     while (j < len)
13     {
14         if (i == -1 || src[j] == src[i])
15         {
16             j++;
17             i++;
18             next[j] = i;
19         }
20         else i = next[i];
21     }
22 }
23 int main()
24 {
25     int C = 1;
26     int t;
27     scanf("%d", &t);
28     while (t--)
29     {
30         scanf("%s", des);
31         int len = strlen(des);
32         GetNext(Next, des, len);
33         int cnt = 0;
34         int ll = Next[len];
35         while (ll)
36         {
37             ans[cnt++] = len - ll;
38             ll = Next[ll];
39         }
40         ans[cnt++] = len;
41         printf("Case #%d: %d
", C++,cnt);
42         for (int i = 0; i < cnt; i++)
43         {
44             if (i) printf(" ");
45             printf("%d", ans[i]);
46         }
47         printf("
");
48     }
49     return 0;
50 }

View Code

18、HDU 3613 Best Reward

　　题意：给出一个由26种字母组成的字符串，每种字母有权值，当一个串是回文串的时候，它的权值是其中所有字母的权值之和，否则是0。现在要将这个字符串切成两段，问两段的权值和最大是多少。

　　思路：扩展KMP模板。将原串s1反转得到s2，然后进行用s1对s2进行扩展KMP匹配, 得到extend, 对于s1的前i个字符如果和s2的后i个字符相等即extend[len - i] == i则前i个字符为回文串, 判断后len - i个字符是否是回文串用s2对s1进行扩展KMP即可

 1 //将原串s1反转得到s2，然后进行s1, s2扩展KMP匹配, 得到extend, 对于s1的前i个字符如果和s2的后i个字符相等即extend[len - i] == i则前i个字符为回文串, 判断后len - i个字符是否是回文串用s2, s1进行扩展KMP即可
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<string>
 6 #include<algorithm>
 7 #define INF 0x3f3f3f3f;
 8 using namespace std;
 9 
10 const int MAX = 500000 + 10;
11 char s1[MAX], s2[MAX];
12 int Next[MAX], extend1[MAX], extend2[MAX];
13 int sum[MAX], val[27];
14 //extend[i]表示目标串从i开始的后缀和模式串的前缀的最长公共长度
15 void get_next(char *P, int len)
16 {
17     int k = 0, i = 1;
18     Next[0] = len;//可有可无,因为用不上 
19     while (k + 1<len && P[k] == P[k + 1])++k;
20     Next[1] = k;//这里预先算好next[1]是因为不能k=0,否则next[i-k]=next[i]不是已算好的 
21     k = 1;
22     while (++i<len)
23     {//和EKMP的过程一样 
24         int maxr = k + Next[k] - 1;
25         Next[i] = min(Next[i - k], max(maxr - i + 1, 0));//这里是扩展KMP的精髓,即算法核心思想就是这
26         while (i + Next[i]<len && P[Next[i]] == P[i + Next[i]])++Next[i];
27         if (i + Next[i]>k + Next[k])k = i;
28     }
29 }
30 
31 void EKMP(char *P, char *T, int *extend)
32 {
33     int lenP = strlen(P);
34     int lenT = strlen(T);
35     get_next(P, lenP);
36     int k = 0, i = 0;
37     int len = min(lenP, lenT);
38     while (k<len && P[k] == T[k])++k;
39     extend[0] = k;
40     k = 0;
41     while (++i<lenT)
42     {
43         int maxr = k + extend[k] - 1;
44         extend[i] = min(Next[i - k], max(maxr - i + 1, 0));//next[i-k]是a与b从i开始的可能已经匹配的长度
45         while (i + extend[i]<lenT &&extend[i]<lenP&&P[extend[i]] == T[i + extend[i]])++extend[i];//这里是扩展KMP的精髓,即算法核心思想就是这
46         if (i + extend[i]>k + extend[k])k = i;
47         //int pp = k + extend[k] - 1, ll = Next[i - k];
48         //if (i - 1 + ll >= pp)
49         //{
50         //    int j = max(0, pp - i + 1);
51         //    while (i + j < lenT&&j < lenP&&T[i + j] == P[j]) j++;
52         //    extend[i] = j;
53         //    k = i;
54         //}
55         //else extend[i] = ll;
56     }
57 }
58 
59 int main()
60 {
61     int n;
62     cin >> n;
63     while (n--)
64     {
65         for (int i = 0; i<26; ++i)cin >> val[i];
66         scanf("%s", s1);
67         int len = strlen(s1);
68         for (int i = 1; i <= len; ++i)
69         {
70             sum[i] = sum[i - 1] + val[s1[i - 1] - 'a'];//记录前缀价值和
71             s2[i - 1] = s1[len - i];//得到原串的反转
72         }
73         EKMP(s1, s2, extend1);
74         EKMP(s2, s1, extend2);
75         int ans = 0, temp = 0;
76         for (int i = 1; i<len; ++i)
77         {
78             if (extend1[len - i] == i)temp += sum[i];//表示前i个字符是回文串
79             if (extend2[i] == len - i)temp += sum[len] - sum[i];//表示后len-i个字符为回文串
80             if (temp>ans)ans = temp;
81             temp = 0;
82         }
83         cout << ans << endl;
84     }
85     return 0;
86 }

View Code

19、poj 3376 Finding Palindromes

　　题意：给你N个字符串, 你可以两两连接得到N * N个字符串, 问之中回文串的数量. N个字符串的长度和加起来不超过2000000.

　　思路：扩展KMP+字典树

假如我们把其中一个翻转，若此时，短的那个串是长的那个的前缀，而长的那个串后面剩余的后缀恰好是个回文串，那这两个串连起来就是个回文串了。比如abc和abacba连接，我们把后一个串翻转，得到abcaba，abc为其前缀，而aba是个回文串，那么连起来就是个回文串。

那我们就把所有的串插入到trie中，然后再用所有的反串去匹配。匹配的过程中，走到任意一个节点，而这个节点有可能是若干个串的结尾，那么此时判反串匹配位置下面剩余的部分是否回文。如果是的，ans就加上以这个节点为结尾的原串的个数（这个插入的时候就可以统计进去了）。如果走完了，还没走到叶子节点，那么就要看走到的节点下的子树（其实是以前面走过的路径为前缀的字符串剩下的一些后缀）有多少是回文的了（这个先预处理所有的串的后缀有哪些是回文的，然后在插入的时候统计到节点上）。

————————摘自：http://blog.csdn.net/pi9nc/article/details/12524647

  1 #include<stdio.h>  
  2 #include<algorithm>  
  3 #include<string.h>  
  4 #define ll __int64  
  5 #include<vector>  
  6 using namespace std;
  7 
  8 const int maxn = 2222222;
  9 char vec[maxn];
 10 int g[maxn], nxt[maxn];
 11 bool st[maxn];
 12 int extend[maxn], Next[maxn];
 13 void get_Next(const char *P)
 14 {
 15     int len = strlen(P);
 16     int k = 0, i = 1;
 17     Next[0] = len;//可有可无,因为用不上 
 18     while (k + 1<len && P[k] == P[k + 1])++k;
 19     Next[1] = k;//这里预先算好next[1]是因为不能k=0,否则next[i-k]=next[i]不是已算好的 
 20     k = 1;
 21     while (++i<len)
 22     {//和EKMP的过程一样 
 23         int maxr = k + Next[k] - 1;
 24         Next[i] = min(Next[i - k], max(maxr - i + 1, 0));//这里是扩展KMP的精髓,即算法核心思想就是这
 25         while (i + Next[i]<len && P[Next[i]] == P[i + Next[i]])++Next[i];
 26         if (i + Next[i]>k + Next[k])k = i;
 27     }
 28 }
 29 
 30 void EXKMP(char *T, char *P)
 31 {
 32     int lenT = strlen(T), lenP = strlen(P);
 33     int k = 0, i = 0;
 34     int len = min(lenP, lenT);
 35     while (k<len && P[k] == T[k])++k;
 36     extend[0] = k;
 37     k = 0;
 38     while (++i<lenT)
 39     {
 40         int maxr = k + extend[k] - 1;
 41         extend[i] = min(Next[i - k], max(maxr - i + 1, 0));//next[i-k]是a与b从i开始的可能已经匹配的长度
 42         while (i + extend[i]<lenT &&extend[i]<lenP&&P[extend[i]] == T[i + extend[i]])++extend[i];//这里是扩展KMP的精髓,即算法核心思想就是这
 43         if (i + extend[i]>k + extend[k])k = i;
 44     }
 45 }
 46 
 47 int tot = 0, c[maxn][26], cnt[maxn], val[maxn];
 48 //cnt[i]记录从i到叶子有多少回文串；val[i]表示在该点结束的字符串的个数
 49 int new_node()
 50 {
 51     int i;
 52     for (i = 0; i < 26; i++) c[tot][i] = 0;
 53     cnt[tot] = val[tot] = 0;
 54     return tot++;
 55 }
 56 
 57 void insert(char *s)
 58 {
 59     int len = strlen(s), i, now = 0;
 60     for (i = 0; i < len; i++)
 61     {
 62         int k = s[i] - 'a';
 63         if (!c[now][k]) c[now][k] = new_node();
 64         now = c[now][k];
 65         if (i + 1 < len && extend[i + 1] == len - i - 1)
 66         {//s[i+1]~s[len-1]为回文串
 67             cnt[now] ++;
 68         }
 69     }
 70     cnt[now] ++;
 71     val[now] ++;
 72 }
 73 
 74 ll ans = 0;
 75 
 76 void cal(int len)
 77 {
 78     int j, i, now = 0;
 79     st[len + 1] = 1;
 80     for (j = 1; j <= len; j++)
 81     {
 82         if (st[j]) now = 0;
 83         int k = vec[j] - 'a';
 84         if (!c[now][k])
 85         {
 86             now = 0;
 87             j = nxt[j] - 1;
 88             continue;
 89         }
 90         now = c[now][k];
 91         if (!st[j + 1] && g[j + 1]) ans += (ll)val[now];
 92         if (st[j + 1])
 93         {
 94             ans += (ll)cnt[now];
 95             now = 0;
 96         }
 97     }
 98 }
 99 
100 char s1[maxn], s[maxn];
101 
102 int main()
103 {
104     int n, i, j, k;
105     while (~scanf("%d", &n))
106     {
107         tot = 0;
108         new_node();//建立Tire根结点
109         int t = 0;
110         for (i = 1; i <= n; i++)
111         {
112             scanf("%d%s", &j, s);
113             strcpy(s1, s);
114             int len = strlen(s);
115             reverse(s1, s1 + len);//反转
116             get_Next(s1);
117             EXKMP(s, s1);//s1匹配s，得到s后缀回文串的长度
118             insert(s);//插入原串
119             get_Next(s);
120             EXKMP(s1, s);//s匹配s1，得到s前缀回文串的长度
121             st[t + 1] = 1;//起点
122             for (j = 0; j < len; j++)
123             {
124                 if (extend[j] == len - j) g[++t] = 1;//如果s[0]~s[j]为回文串，则标记
125                 else g[++t] = 0;
126                 vec[t] = s1[j];//记录反转串
127                 if (j) st[t] = 0;
128             }
129         }
130         int last = t + 1;//最后一个反转串的下一个，结束标志
131         for (i = t; i >= 1; i--)
132         {
133             nxt[i] = last;//记录当前反转串的下一个反转串
134             if (st[i]) last = i;
135         }
136         ans = 0;
137         cal(t);
138         printf("%I64d
", ans);
139     }
140     return 0;
141 }

View Code

20、hdu 4763 Theme Section

　　题意：找到给出字符串的一个子串，其是该字符串的前缀和后缀，且在字符串中间出现过(和前缀后缀不重合)，求其最大长度。

　　思路：根据next数组性质，递归找next[len],判断中间是否出现过。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int maxp = 1000010;
 5 char p[maxp];
 6 int Next[maxp];
 7 void GetNext(int *next, char *src, int len)
 8 {//next和src都从下标0开始存储
 9     next[0] = -1;
10     int j = 0, i = -1;
11     while (j < len)
12     {
13         if (i == -1 || src[j] == src[i])
14         {
15             j++;
16             i++;
17             next[j] = i;
18         }
19         else i = next[i];
20     }
21 }
22 int main()
23 {
24     int n;
25     scanf("%d", &n);
26     for (int i = 1; i <= n; i++)
27     {
28         scanf("%s", p);
29         int len = strlen(p);
30         GetNext(Next, p, len);
31         int ll = Next[len];
32         int ans = 0;
33         while (ll > 0)
34         {
35             bool can = false;
36             for (int i = ll; i < len - ll; i++)
37             {
38                 if (p[i] == p[0])
39                 {
40                     int j = i, k = 0;
41                     while (k<ll&&p[j] == p[k]) j++, k++;
42                     if (k == ll)
43                     {
44                         can = true;
45                         break;
46                     }
47                 }
48             }
49             if (can)
50             {
51                 ans = ll;
52                 break;
53             }
54             ll = Next[ll];
55         }
56         printf("%d
", ans);
57     }
58     return 0;
59 }

View Code