hdu 3336
题意：输入一个字符串求每个前缀在串中出现的次数和
sol:只要稍微理解下next 数组的含义就知道只要把每个有意义的next值得个数加起来即可
PS：网上有dp解法orz，dp[i]表示以i为前缀串结尾的前缀串的总和，方程很容易写出
//字符串上KMP(水)
//从前向后扫，失配函数的位置就是一个前缀的位置减1
//加起来就好了
// by acvc
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX = 200000;
const int MOD = 10007;
char str[MAX];
int next[MAX],vis[MAX];
int main()
{
int cas,n;
scanf("%d",&cas);
while(cas--)
{
scanf("%d %s",&n,str);
next[0]=next[1]=0;
for(int i=1;i<n;i++)
{
int j=next[i];
while(j&&str[i]!=str[j]) j=next[j];
if(str[i]==str[j])
next[i+1]=j+1;
else next[i+1]=0;
}
int ans=0,cnt=0;
for(int i=0;i<n;i++)
{
if(next[i])
{
// cnt++;
ans=(ans+2)%MOD;
}
else
ans=(ans+1)%MOD;
}
if(next[n]) ans=(ans+1)%MOD;
printf("%d ",(ans)%MOD);
}
return 0;
//从前向后扫，失配函数的位置就是一个前缀的位置减1
//加起来就好了
// by acvc
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX = 200000;
const int MOD = 10007;
char str[MAX];
int next[MAX],vis[MAX];
int main()
{
int cas,n;
scanf("%d",&cas);
while(cas--)
{
scanf("%d %s",&n,str);
next[0]=next[1]=0;
for(int i=1;i<n;i++)
{
int j=next[i];
while(j&&str[i]!=str[j]) j=next[j];
if(str[i]==str[j])
next[i+1]=j+1;
else next[i+1]=0;
}
int ans=0,cnt=0;
for(int i=0;i<n;i++)
{
if(next[i])
{
// cnt++;
ans=(ans+2)%MOD;
}
else
ans=(ans+1)%MOD;
}
if(next[n]) ans=(ans+1)%MOD;
printf("%d ",(ans)%MOD);
}
return 0;
}
hdu 1358
题意：给出一个字符串求出每个前缀的最小周期
sol:next数组理解题目稍微想想就知道t=(len-next[len])
//kmp小深入题目
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 10000000+10;
char str[MAX]; int next[MAX]; //失配函数
int main()
{
int n,cnt=0;
while(scanf("%d",&n)>0)
{
scanf("%s",str);
next[0]=next[1]=0;
for(int i=1;i<n;i++)
{
int j=next[i];
while(j&&str[i]!=str[j]) j=next[j];
if(str[i]==str[j]) next[i]=j+1;
else next[i]=0;
}
printf("Test case #%d ",++cnt);
for(int i=2;i<=n;i++)
{
if(next[i]&&i%(i-next[i])==0)
printf("%d %d ",i,i%(i-next[i]));
}
}
return 0;
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 10000000+10;
char str[MAX]; int next[MAX]; //失配函数
int main()
{
int n,cnt=0;
while(scanf("%d",&n)>0)
{
scanf("%s",str);
next[0]=next[1]=0;
for(int i=1;i<n;i++)
{
int j=next[i];
while(j&&str[i]!=str[j]) j=next[j];
if(str[i]==str[j]) next[i]=j+1;
else next[i]=0;
}
printf("Test case #%d ",++cnt);
for(int i=2;i<=n;i++)
{
if(next[i]&&i%(i-next[i])==0)
printf("%d %d ",i,i%(i-next[i]));
}
}
return 0;
}
hdu1711
题意：给出两个数组，求出b在a中最先匹配的位置
sol：KMP裸题
1 //裸题
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 using namespace std;
6 const int MAX = 1e6+10;
7 int next[MAX];
8 int a[MAX],b[MAX];
9 int main()
10 {
11 int cas,n,m;
12 scanf("%d",&cas);
13 while(cas--)
14 {
15 scanf("%d %d",&n,&m);
16 for(int i=0;i<n;i++) scanf("%d",&a[i]);
17 for(int j=0;j<m;j++) scanf("%d",&b[j]);
18 next[1]=next[0]=0;
19 for(int i=1;i<m;i++)
20 {
21 int j=next[i];
22 while(j&&b[i]!=b[j]) j=next[j];
23 if(b[i]==b[j]) next[i+1]=j+1;
24 else next[i+1]=0;
25 }
26 int cur=0,flag=0;
27 for(int i=0;i<n;i++)
28 {
29 while(cur&&a[i]!=b[cur]) cur=next[cur];
30 if(a[i]==b[cur]) cur++;
31 if(cur==m)
32 {
33 flag=1;
34 printf("%d ",i-cur+2);
35 break;
36 }
37 }
38 if(!flag) printf("-1 ");
39 }
40 return 0;
2 #include<cstring>
3 #include<cstdio>
4 #include<algorithm>
5 using namespace std;
6 const int MAX = 1e6+10;
7 int next[MAX];
8 int a[MAX],b[MAX];
9 int main()
10 {
11 int cas,n,m;
12 scanf("%d",&cas);
13 while(cas--)
14 {
15 scanf("%d %d",&n,&m);
16 for(int i=0;i<n;i++) scanf("%d",&a[i]);
17 for(int j=0;j<m;j++) scanf("%d",&b[j]);
18 next[1]=next[0]=0;
19 for(int i=1;i<m;i++)
20 {
21 int j=next[i];
22 while(j&&b[i]!=b[j]) j=next[j];
23 if(b[i]==b[j]) next[i+1]=j+1;
24 else next[i+1]=0;
25 }
26 int cur=0,flag=0;
27 for(int i=0;i<n;i++)
28 {
29 while(cur&&a[i]!=b[cur]) cur=next[cur];
30 if(a[i]==b[cur]) cur++;
31 if(cur==m)
32 {
33 flag=1;
34 printf("%d ",i-cur+2);
35 break;
36 }
37 }
38 if(!flag) printf("-1 ");
39 }
40 return 0;
41 }
hdu2087
题意：给定串1和串2求串2在串1中出现的顺序
sol；裸KMP从前向后扫一遍kmp就好了
1 #include<cstring>
2 #include<algorithm>
3 #include<cstdio>
4 using namespace std;
5 const int MAX = 1000+10;
6 char str1[MAX],str2[MAX];
7 int next[MAX];
8 int main()
9 {
10 while(scanf("%s",str1)&&strcmp(str1,"#"))
11 {
12 int ans=0;
13 scanf("%s",str2);
14 int n=strlen(str2); next[0]=next[1]=0;
15 for(int i=1;i<n;i++)
16 {
17 int j=next[i];
18 while(j&&str2[i]!=str2[j]) j=next[j];
19 if(str2[i]==str2[j]) next[i+1]=j+1;
20 else next[i+1]=0;
21 }
22 int len=strlen(str1); int j=0;
23 for(int i=0;i<len;i++)
24 {
25 while(j&&str1[i]!=str2[j]) j=next[j];
26 if(str1[i]==str2[j]) j++;
27 if(j==n)
28 {
29 ans++;
30 j=0;
31 }
32 }
33 printf("%d ",ans);
34 }
35 return 0;
2 #include<algorithm>
3 #include<cstdio>
4 using namespace std;
5 const int MAX = 1000+10;
6 char str1[MAX],str2[MAX];
7 int next[MAX];
8 int main()
9 {
10 while(scanf("%s",str1)&&strcmp(str1,"#"))
11 {
12 int ans=0;
13 scanf("%s",str2);
14 int n=strlen(str2); next[0]=next[1]=0;
15 for(int i=1;i<n;i++)
16 {
17 int j=next[i];
18 while(j&&str2[i]!=str2[j]) j=next[j];
19 if(str2[i]==str2[j]) next[i+1]=j+1;
20 else next[i+1]=0;
21 }
22 int len=strlen(str1); int j=0;
23 for(int i=0;i<len;i++)
24 {
25 while(j&&str1[i]!=str2[j]) j=next[j];
26 if(str1[i]==str2[j]) j++;
27 if(j==n)
28 {
29 ans++;
30 j=0;
31 }
32 }
33 printf("%d ",ans);
34 }
35 return 0;
36 }
poj2406
题意：给定一个串求出串的最小周期
los:失配函数裸题啊
1 //kmp-shui
2 #include<cstring>
3 #include<algorithm>
4 #include<cstdio>
5 using namespace std;
6 const int MAX = 1e6+10;
7 char str[MAX]; int next[MAX];
8 int main()
9 {
10 int ans;
11 while(1)
12 {
13 gets(str); if(!strcmp(str,".")) break;
14 int n=strlen(str); next[0]=next[1]=0;
15 for(int i=1;i<n;i++)
16 {
17 int j=next[i];
18 while(j&&str[i]!=str[j]) j=next[j];
19 if(str[i]==str[j]) next[i+1]=j+1;
20 else next[i+1]=0;
21 }
22 if(n%(n-next[n])==0)
23 printf("%d ",n/(n-next[n]));
24 else printf("1 ");
25 }
26 return 0;
2 #include<cstring>
3 #include<algorithm>
4 #include<cstdio>
5 using namespace std;
6 const int MAX = 1e6+10;
7 char str[MAX]; int next[MAX];
8 int main()
9 {
10 int ans;
11 while(1)
12 {
13 gets(str); if(!strcmp(str,".")) break;
14 int n=strlen(str); next[0]=next[1]=0;
15 for(int i=1;i<n;i++)
16 {
17 int j=next[i];
18 while(j&&str[i]!=str[j]) j=next[j];
19 if(str[i]==str[j]) next[i+1]=j+1;
20 else next[i+1]=0;
21 }
22 if(n%(n-next[n])==0)
23 printf("%d ",n/(n-next[n]));
24 else printf("1 ");
25 }
26 return 0;
27 }
poj 2752
题意：给定一个串求出满足既是前缀又是后缀的串的起始位置
sol：又是一发next数组加深题目，很明显next数组指向的是最长的一个前缀串，所以最后一个指针指向的next就是一个最长前缀
之后从这个最长前缀末尾开始下一个指针又是前缀的最长前缀，而后缀和前缀相同，所以这个是第二长的前缀，只要递归结束即可
1 //kmp题目shui by acvc
2 //kmp每次都是求的最长的前缀
3 #include<cstring>
4 #include<algorithm>
5 #include<cstdio>
6 #include<vector>
7 using namespace std;
8 const int MAX = 400000+10;
9 int next[MAX];
10 char str[MAX];
11 vector<int> s;
12 int main()
13 {
14 while(scanf("%s",str)!=EOF)
15 {
16 s.clear();
17 int n=strlen(str); next[0]=0,next[1]=0;
18 for(int i=1;i<n;i++)
19 {
20 int j=next[i];
21 while(j&&str[i]!=str[j]) j=next[j];
22 if(str[i]==str[j]) next[i+1]=j+1;
23 else next[i+1]=0;
24 }
25 //for(int i=0;i<=n;i++) printf("%d ",next[i]);
26 // printf(" ");
27 int j=strlen(str);
28 while(j)
29 {
30 s.push_back(j);
31 j=next[j];
32 }
33 for(int i=s.size()-1;i>=0;i--)
34 {
35 if(i==s.size()-1) printf("%d",s[i]);
36 else printf(" %d",s[i]);
37 }
38 printf(" ");
39 }
40 return 0;
41 }
3 #include<cstring>
4 #include<algorithm>
5 #include<cstdio>
6 #include<vector>
7 using namespace std;
8 const int MAX = 400000+10;
9 int next[MAX];
10 char str[MAX];
11 vector<int> s;
12 int main()
13 {
14 while(scanf("%s",str)!=EOF)
15 {
16 s.clear();
17 int n=strlen(str); next[0]=0,next[1]=0;
18 for(int i=1;i<n;i++)
19 {
20 int j=next[i];
21 while(j&&str[i]!=str[j]) j=next[j];
22 if(str[i]==str[j]) next[i+1]=j+1;
23 else next[i+1]=0;
24 }
25 //for(int i=0;i<=n;i++) printf("%d ",next[i]);
26 // printf(" ");
27 int j=strlen(str);
28 while(j)
29 {
30 s.push_back(j);
31 j=next[j];
32 }
33 for(int i=s.size()-1;i>=0;i--)
34 {
35 if(i==s.size()-1) printf("%d",s[i]);
36 else printf(" %d",s[i]);
37 }
38 printf(" ");
39 }
40 return 0;
41 }
poj 2185
题意：输入一个矩阵由字符组成，求出矩阵的最小组成单位。
sol:网上好多代码都是错的，第一次学被误解了，今天重新修改这道题，其实找出每一行的周期串记录下个数,最后等于行数的肯定就是最小的宽。
求高直接公式就好了，
1 /************************
2 * zhuyuqi *
3 * QQ:1113865149 *
4 * worfzyq@gmail.com *
5 *************************/
6 #include <cstdio>
7 #include <cstring>
8 #include <algorithm>
9 #include <cmath>
10 #include <vector>
11 #include <list>
12 #include <queue>
13 using namespace std;
14 const int MAX = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 char str[MAX][80];
17 int next[MAX],ML[MAX],vis[MAX];
18 int main()
19 {
20
21 int n,m; int L,R;
22 while(scanf("%d %d",&n,&m)==2) {
23 for(int i=1;i<=n;i++) {
24 scanf("%s",str[i]+1);
25 }
26 // for(int i=1;i<=n;i++) printf("%s ",str[i]+1);
27 memset(ML,0,sizeof(ML));
28 if(m>1) {
29 for(int i=1;i<=n;i++) {
30 next[1]=0; int j=0; memset(vis,0,sizeof(vis));
31 for(int k=2;k<=m;k++) {
32 while(j&&str[i][k]!=str[i][j+1]) j=next[j];
33 if(str[i][k]==str[i][j+1]) j++;
34 next[k]=j;
35 }
36 int x=m;
37 // for(int k=1;k<=m;k++) printf("%d ",next[k]); printf(" ");
38 while(x) {
39 // if(x==1) break;
40 if(!vis[m-next[x]])
41 ML[m-next[x]]++; x=next[x]; vis[x-next[x]]=1;
42 }
43 }
44 for(int i=1;i<=m;i++) if(ML[i]==n) {
45 L=i; break;
46 }
47 } else L=1;
48 next[1]=0; int j=0;
49 for(int i=2;i<=n;i++) {
50 while(j&&strcmp(str[i]+1,str[j+1]+1)) j=next[j];
51 // printf("%d %d ",i,j+1);
52 if(!strcmp(str[i]+1,str[j+1]+1)) j++;
53 // printf("%d %d ",next[i],j);
54 next[i]=j;
55 }
56 //printf("%d %d ",L,n-next[n]);
57 printf("%d ",(n-next[n])*L);
58
59 }
60
61 return 0;
62 }
2 * zhuyuqi *
3 * QQ:1113865149 *
4 * worfzyq@gmail.com *
5 *************************/
6 #include <cstdio>
7 #include <cstring>
8 #include <algorithm>
9 #include <cmath>
10 #include <vector>
11 #include <list>
12 #include <queue>
13 using namespace std;
14 const int MAX = 1e4+10;
15 const int inf = 0x3f3f3f3f;
16 char str[MAX][80];
17 int next[MAX],ML[MAX],vis[MAX];
18 int main()
19 {
20
21 int n,m; int L,R;
22 while(scanf("%d %d",&n,&m)==2) {
23 for(int i=1;i<=n;i++) {
24 scanf("%s",str[i]+1);
25 }
26 // for(int i=1;i<=n;i++) printf("%s ",str[i]+1);
27 memset(ML,0,sizeof(ML));
28 if(m>1) {
29 for(int i=1;i<=n;i++) {
30 next[1]=0; int j=0; memset(vis,0,sizeof(vis));
31 for(int k=2;k<=m;k++) {
32 while(j&&str[i][k]!=str[i][j+1]) j=next[j];
33 if(str[i][k]==str[i][j+1]) j++;
34 next[k]=j;
35 }
36 int x=m;
37 // for(int k=1;k<=m;k++) printf("%d ",next[k]); printf(" ");
38 while(x) {
39 // if(x==1) break;
40 if(!vis[m-next[x]])
41 ML[m-next[x]]++; x=next[x]; vis[x-next[x]]=1;
42 }
43 }
44 for(int i=1;i<=m;i++) if(ML[i]==n) {
45 L=i; break;
46 }
47 } else L=1;
48 next[1]=0; int j=0;
49 for(int i=2;i<=n;i++) {
50 while(j&&strcmp(str[i]+1,str[j+1]+1)) j=next[j];
51 // printf("%d %d ",i,j+1);
52 if(!strcmp(str[i]+1,str[j+1]+1)) j++;
53 // printf("%d %d ",next[i],j);
54 next[i]=j;
55 }
56 //printf("%d %d ",L,n-next[n]);
57 printf("%d ",(n-next[n])*L);
58
59 }
60
61 return 0;
62 }