1 //在BT5下attack的时候把数值调大点(超过2000）就行了，具体可以参见网上破解无线网密码的文章，就是抓包之后的那步，注入数据包的命令 2 #include "iostream" 3 #include "cstring" 4 using namespace std; 5 #define maxn 1010000 6  7 int wa[maxn],wb[maxn],wv[maxn],wws[maxn]; 8 int rank[maxn],height[maxn]; 9 int r[maxn],sa[maxn],ans[maxn],st[maxn],ln[maxn];10 int n,len,tl;11 char ts[maxn];12 13 int cmp(int *r,int a,int b,int l)14 {15     return r[a]==r[b]&&r[a+l]==r[b+l];16 }17 18 void da(int *r,int *sa,int n,int m)19 {20     int i,j,p,*x=wa,*y=wb,*t;21     for(i=0; i<m; i++) wws[i]=0;22     for(i=0; i<n; i++) wws[x[i]=r[i]]++;23     for(i=1; i<m; i++) wws[i]+=wws[i-1];24     for(i=n-1; i>=0; i--) sa[--wws[x[i]]]=i;25     for(j=1,p=1; p<n; j*=2,m=p)26     {27 28         for(p=0,i=n-j; i<n; i++) y[p++]=i;29         for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;30         for(i=0; i<n; i++) wv[i]=x[y[i]];31         for(i=0; i<m; i++) wws[i]=0;32         for(i=0; i<n; i++) wws[wv[i]]++;33         for(i=1; i<m; i++) wws[i]+=wws[i-1];34         for(i=n-1; i>=0; i--) sa[--wws[wv[i]]]=y[i];35         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)36             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;37     }38     return;39 }40 41 void calheight(int *r,int *sa,int n)42 {43     int i,j,k=0;44     for(i=1; i<=n; i++) rank[sa[i]]=i;45     for(i=0; i<n; height[rank[i++]]=k)46         for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);47     return;48 }49 50 int main()51 {52     ios::sync_with_stdio(false);53     cin>>n;54     len=0;55     for (int i=1;i<=n;i++)56     {57         st[i]=len;58         cin>>ts;59         tl=strlen(ts);60         ln[i]=tl;61         for (int j=len;j<len+tl;j++)62         {63             char ch=ts[j-len];64             int tn=ch;65             r[j]=tn;66         }67         len+=tl;68         r[len]=1;69         len++;70     }71     r[len]=0;72 73     da(r,sa,len+1,200);74     calheight(r,sa,len);75 76     //for (int i=0;i<=len+1;i++)77     //    cout<<height[i]<<" ";78     //cout<<endl;79     for (int i=1;i<=n;i++)80     {81         int tmp=rank[st[i]];82         int tl=tmp,tr=tmp+1,tlen=ln[i];83         while ((height[tl]>=tlen)&&(tl>=0))      tl--;84         while ((height[tr]>=tlen)&&(tr<=len))   tr++;85         cout<<tr-tl<<endl;86     }87 88     return 0;89 }