学习地址：http://blog.csdn.net/yxuanwkeith/article/details/50636898

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=400010;char s[maxn],s1[maxn],s2[maxn];int ans,tax[maxn],tp[maxn],sa[maxn],ra[maxn],H[maxn],n,m;void rsort(){    for(int i=0;i<=m;++i)tax[i]=0;    for(int i=1;i<=n;++i)tax[ra[tp[i]]]++;    for(int i=1;i<=m;++i)tax[i]+=tax[i-1];    for(int i=n;i>=1;--i)sa[tax[ra[tp[i]]]--]=tp[i];}int cmp(int x,int y,int w){
   return tp[x]==tp[y]&&tp[x+w]==tp[y+w];}void pre(){    for(int i=1;i<=n;++i)ra[i]=s[i]-'a'+1,tp[i]=i;    m=32;rsort();    for(int w=1,p=1,i;p
          
           w)tp[++p]=sa[i]-w; rsort();swap(ra,tp);ra[sa[1]]=p=1; //这里换一下才方便由这一次的ra得到下一次的ra; for(i=2;i<=n;++i)ra[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p; } int j,k=0; for(int i=1;i<=n;H[ra[i++]]=k) for(k=k?k-1:k,j=sa[ra[i]-1];s[i+k]==s[j+k];++k);}int main(){ scanf("%s%s",s1+1,s2+1); int len1=strlen(s1+1),len2=strlen(s2+1); for(int i=1;i<=len1;++i)s[i]=s1[i]; s[len1+1]='a'+30; for(int i=1;i<=len2;++i)s[i+len1+1]=s2[i]; n=len1+len2+1; pre();ans=0; //for(int i=1;i<=n;++i)cout<
           
            <<' '<
            
             <