il void getsa(){ int m=128;//初始m等于字符种类数 for(int i=1;i<=n;i++)c[x[i]=s[i-1]]++; for(int i=2;i<=m;i++)c[i]+=c[i-1]; for(int i=n;i;i--)sa[c[x[i]]--]=i; //x[i]是第i个元素的第一关键字 for(int k=1;k<=n;k<<=1){ int num=0;//y[i]表示第二关键字为i的字符串第一关键字的位置 for(int i=n-k+1;i<=n;i++)y[++num]=i;//表示没有第二关键字的字符串，放在最前面 for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;//sa[i]>k表示sa[i]为sa[i]-k的第二关键字 for(int i=1;i<=m;i++)c[i]=0; for(int i=1;i<=n;i++)c[x[i]]++; for(int i=2;i<=m;i++)c[i]+=c[i-1]; for(int i=n;i;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0; swap(x,y);x[sa[1]]=1;num=1; for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num; if(num==n)break; m=num; } for(int i=1;i<=n;i++)rk[sa[i]]=i;}il void getheight(){ int k=0; for(int i=1;i<=n;i++){ if(rk[i]==1)continue; if(k)k--; int j=sa[rk[i]-1]; while(j+k<=n&&i+k<=n&&s[i+k-1]==s[j+k-1])k++; h[i]=k; } for(int i=1;i<=n;i++)height[rk[i]]=h[i];}//超级容易错，警惕啊！！每个数组的含义不能乱！菜哭辽 
