//聪神说：做完了题目记得总结，方便以后复习。
SPOJ SUBST1
题目链接：点击打开链接
题意：给一个字符串，求不同子串个数。
思路：假设所有子串都不同，答案为len*(len+1)/2;然而不是这样… 下面我们就找出重复的子串：
首先先将后缀排序，对于后缀i能生成len-sa[i]个子串，，这其中有height[i]个子串与第i-1个后缀生成的子串重复了；
所以答案为 len*(len+1)/2-segema(height[i]) 。
cpp代码:
//spoj disubstr#include <cstring>#include <iostream>#include <cstdio>#include <vector>using namespace std;const int MAXN =1010;int t1[MAXN],t2[MAXN],c[MAXN];bool cmp(int *r ,int a,int b ,int l){return r[a]==r[b]&&r[a+1]==r[b+1];}void da(int sa[],int Rank[],int str[],int height[],int n,int m){n++;int i,j,p,*x=t1,*y=t2;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++)c[x[i]=str[i]]++;for(i=1;i<m;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i–)sa[–c[x[i]]]=i;for(j=1;j<=n;j<<=1){p=0;for(i=n-j;i<n;i++)y[p++]=i;for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;for(i=0;i<m;i++)c[i]=0;for(i=0;i<n;i++)c[x[y[i]]]++;for(i=1;i<m;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i–)sa[–c[x[y[i]]]]=y[i];swap(x,y);p=1;x[sa[0]]=0;for(i=1;i<n;i++){x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;//x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}if(p>=n) break;m=p;}int k=0;n–;for(i=0;i<=n;i++ )Rank[sa[i]]=i;for(i=0;i<n;i++){if(k)k–;j=sa[Rank[i]-1];while(str[i+k]==str[j+k])k++;height[Rank[i]]=k;}}char st[MAXN];int Rank[MAXN],str[MAXN],sa[MAXN],height[MAXN];int main(){//freopen("data.in","r",stdin);int T;scanf("%d",&T);while(T–){scanf("%s",st);int l=strlen(st);for(int i=0;i<=l;i++){str[i]=st[i];}da(sa,Rank,str,height,l,128);long long ans=(long long)(l+1)*(l)/2;for(int i=2;i<=l;i++){ans-=height[i];}cout<<ans<<endl;}return 0;}
POJ 2406:
题意：给定字符串，问最多能找出几个循环节。
思路：寻找最大的k使得 lcp(0,k)=k 并且 lcp(0,k)%k==0;
但是我是用kmp写的。。。 next[n] 即为 将字符串反转之后lcp(0,len-(next[n]))==next[n]的最大值。
cpp：
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int MAXN =2000000;int Next[MAXN];char str[MAXN];void get_Next(int len){int i=0,j=-1;Next[i]=j;while(i<len){if(str[i]==str[j]||j==-1){++i,++j;Next[i]=j;}else {j=Next[j];}}}int main(){freopen("data.in","r",stdin);while(~scanf("%s",str)){//cout<<str<<endl;if(str[0]=='.') break;int len=strlen(str);get_Next(len);if(len%(len-Next[len])==0)printf("%d\n",len/(len-Next[len]));else puts("1");}return 0;}SPOJ REPEATS
题意：寻找循环次数最多的循环序列，输出循环次数。
思路：
cpp：
#include <cstring>#include <iostream>#include <cstdio>#include <vector>using namespace std;const int MAXN =200010;int t1[MAXN],t2[MAXN],c[MAXN];int str[MAXN],sa[MAXN],Rank[MAXN],height[MAXN];bool cmp(int *r ,int a,int b ,int l){return r[a]==r[b]&&r[a+1]==r[b+1];}void da(int n,int m){n++;int i,j,p,*x=t1,*y=t2;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++)c[x[i]=str[i]]++;for(i=1;i<m;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i–)sa[–c[x[i]]]=i;for(j=1;j<=n;j<<=1){p=0;for(i=n-j;i<n;i++)y[p++]=i;for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;for(i=0;i<m;i++)c[i]=0;for(i=0;i<n;i++)c[x[y[i]]]++;for(i=1;i<m;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i–)sa[–c[x[y[i]]]]=y[i];swap(x,y);p=1;x[sa[0]]=0;for(i=1;i<n;i++){x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;//x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}if(p>=n) break;m=p;}int k=0;n–;for(i=0;i<=n;i++ )Rank[sa[i]]=i;for(i=0;i<n;i++){if(k)k–;j=sa[Rank[i]-1];while(str[i+k]==str[j+k])k++;height[Rank[i]]=k;}}int mm[MAXN];int best[20][MAXN];void initRMQ(int n){mm[0]=-1;for(int i=1;i<=n;i++)mm[i]=((i&(i-1))==0?mm[i-1]+1:mm[i-1]);for(int i=1;i<=n;i++) best[0][i]=i;for(int i=1;i<=mm[n];i++){for(int j=1;j+(1<<i)-1<=n;j++){int a=best[i-1][j];int b=best[i-1][j+(1<<(i-1))];if(height[a]<height[b])best[i][j]=a;else best[i][j]=b;}}}int askRMQ(int a,int b){int t;t=mm[b-a+1];b-=(1<<t)-1;a=best[t][a];b=best[t][b];return height[a]<height[b]?a:b;}int lcp(int a,int b){a=Rank[a];b=Rank[b];if(a>b) swap(a,b);return height[askRMQ(a+1,b)];}char tp[2];int main(){int T,n;//freopen("data.in","r",stdin);scanf("%d",&T);while(T–){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%s",tp);str[i]=tp[0];}int ans=1;str[n]=0;da(n,128);initRMQ(n);for(int i=1;i<n;i++){for(int j=0;j+i<n;j+=i){int k=lcp(j,j+i);int tp=j-(i-k%i);int ttt=k/i+1;if(tp>=0&&lcp(tp,tp+i)>=i){ttt++;}ans=max(ttt,ans);}}cout<<ans<<endl;}return 0;}
哪里有意志存在，哪里就会有出路。
