字符串匹配

KMP

 1 il void gnxt()
 2 {
 3     nxt[1]=0;
 4     for(rg int i=2;j=0;i<=n;++i)
 5     {
 6         while(j && a[i]!=a[j+1]) j=nxt[j];
 7         if(a[i]==a[j+1]) ++j;
 8         nxt[i]=j;
 9     }
10 }
11 
12 il void gf()
13 {
14     for(rg int i=1,j=0;i<=m;++i)
15     {
16         while(j && b[i]!=a[j+1]) j=nxt[j];
17         if(b[i]==a[j+1]) ++j;
18         f[i]=j;
19         //if(f[i]==n) once A in B
20     }
21 }

最小表示法

 1 int i=1,j=2,k;
 2 while(i<=n && j<=n)
 3 {
 4     for(k=0;k<n && s[i+k]==s[j+k];++k);
 5     if(s[i+k]>s[j+j])
 6     {
 7         i=i+k+1;
 8         if(i==j) ++i;
 9     }
10     else
11     {
12         j=j+k+1;
13         if(i==j) ++j;
14     }
15 }
16 for(k,0,n) 
17 {
18     if(s[i+k]<s[j+k])
19     {
20         ans=i;
21         break;
22     }
23     else
24     {
25         ans=j;
26         break;
27     }
28 }

poj1961 period

http://poj.org/problem?id=1961

对于具有N个字符的给定字符串S的每个前缀（每个字符具有介于97和126之间的ASCII代码），我们想知道该前缀是否是周期性字符串。也就是说，对于每个i（2 <= i <= N），我们想要知道最大的K> 1（如果有的话），使得长度为i的S的前缀可以写为A ^K，即A连接K次，对于一些字符串A.当然，我们也想知道期间K.

 1 char a[1000010];
 2 int next[1000010],n,t,c;  
 3 void getnext()
 4 {
 5     for(int i=2,j=0;i<=n;++i)
 6     {
 7         while(j&&a[j+1]!=a[i]) j=next[j];
 8         if(a[j+1]==a[i]) ++j;
 9         next[i]=j;
10     }
11 }
12 int main()
13 {
14     while(cin>>n&&n){
15     scanf("%s",a+1);
16     printf("Test case #%d
",++c);
17     getnext();
18     for(int i=1;i<=n;++i)
19         if(i%(i-next[i])==0&&i>i-next[i])
20             printf("%d %d
",i,i/(i-next[i]));
21     printf("
");
22     }return 0;
23 }