hdu poj KMP简单题目总结

//字符串上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\n",(ans)%MOD);
    }
    return 0;

//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\n",++cnt);
        for(int i=2;i<=n;i++)
        {
            if(next[i]&&i%(i-next[i])==0)
            printf("%d %d\n",i,i%(i-next[i]));
        }
    }
    return 0;

 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\n",i-cur+2);
35                 break;
36             }
37         }
38         if(!flag) printf("-1\n");
39     }
40     return 0;

 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\n",ans);
34     }
35     return 0;

 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/(n-next[n]));
24         else printf("1\n");
25     }
26     return 0;

 1 #include<iostream>
 2 #include<stdio.h>
 3 using namespace std;
 4 char s[10005][80];
 5 int subrow[10005];
 6 int subcol[80];
 7 int next[10005];
 8 int row,col;
 9 int nextrow(int r)
10 {
11     int i=0,j=-1;
12     next[0]=-1;
13     while(i<col)
14     {
15         if(j==-1||s[r][i]==s[r][j])
16         {
17             i++;j++;
18             next[i]=j;
19         }
20         else
21             j=next[j];
22     }
23     return i-next[i];
24 }
25 int nextcol(int c)
26 {
27     int i=0,j=-1;
28     next[0]=-1;
29     while(i<row)
30     {
31         if(j==-1||s[i][c]==s[j][c])
32         {
33             i++;j++;
34             next[i]=j;
35         }
36         else
37             j=next[j];
38     }
39     return i-next[i];
40 }
41 
42 int LCM(int a,int b)
43 {
44     int x=a,y=b;
45     int r=x%y;
46     while(r>0)
47     {
48         x=y;
49         y=r;
50         r=x%y;
51     }
52     return a*b/y;
53 }
54 int main()
55 {
56     while(scanf("%d%d",&row,&col)==2)
57     {
58         for(int i=0;i<row;i++)
59             scanf("%s",s[i]);
60         for(int i=0;i<row;i++)
61             subrow[i]=nextrow(i);
62         for(int i=0;i<col;i++)
63             subcol[i]=nextcol(i);
64         int x=1;
65         for(int i=0;i<row;i++)
66             x=LCM(x,subrow[i]);
67         if(x>col)
68             x=col;
69         int y=1;
70         for(int i=0;i<col;i++)
71             y=LCM(y,subcol[i]);
72         if(y>row)
73             y=row;
74         printf("%d\n",x*y);
75     }
76     return 0;