第一次写后缀数组，真心好难，直接抄代码了，有些地方还不是很理解，先写着，留着以后再看看
/*学习后缀数组真心学习了好久，各种数组的意义往往搞不清楚后来总结出来，应该给每一个数组一个自己理解的实际意义*/ #include<stdio.h> #include<algorithm>using namespace std;const int N=100010;typedef long long ll;int wv[N],ws[N],wa[N],wb[N],rank[N],height[N],sa[N],str[N];int n,m,k,l;bool cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}void da(int *r,int *sa,int n,int m){int i,j,p,*x=wa,*y=wb;for(i=0;i<m;i++) ws[i]=0;for(i=0;i<n;i++) ws[x[i]=r[i]]++;for(i=0;i<m;i++) ws[i]+=ws[i-1];for(i=n-1;i>=0;i–) sa[–ws[x[i]]]=i;for(j=1,p=1;j<n;j<<=1,m=p){for(p=0,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<n;i++) wv[i]=x[y[i]];for(i=0;i<m;i++) ws[i]=0;for(i=0;i<n;i++) ws[wv[i]]++;for(i=1;i<m;i++) ws[i]+=ws[i-1];for(i=n-1;i>=0;i–) sa[–ws[wv[i]]]=y[i];swap(x,y);for(p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}return;}void calheight(int *r,int *sa,int n){int i,j,k=0;for(i=1;i<=n;i++) rank[sa[i]]=i;for(i=0;i<n;height[rank[i++]]=k) for(k?k–:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);return;}ll solve(int num,int len){ll ans=0;int one=0,two=0;if (sa[0]<n) one++;else two++;for(int i=1;i<=len;i++){if(height[i]<num) {if(two>0) ans+=ll(one);one=0;two=0;if(sa[i]<n) one++;else two++;}else{if(sa[i]<n) one++;else two++;}}return ans;}int main(){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifwhile(scanf("%d%d%d",&n,&m,&k)!=EOF){l=n+m+1;for(int i=0;i<n;i++) {scanf("%d",&str[i]);str[i]++;//保证值大于1 }str[n]=10002;//用于分割两个字符串for(int i=n+1;i<l;i++) {scanf("%d",&str[i]);str[i]++;}str[l]=0;da(str,sa,l+1,10003);calheight(str,sa,l);printf("%I64d\n",solve(k,l)-solve(k+1,l));}return 0;}
——————————————————————–分割线——————————————————————————————————–
出去吃了个饭，回来想了一下，终于弄懂了。。。。
看来一个问题很久想不出答案的时候放松放松真的很有必要。
</pre><pre name="code" class="cpp">/*还是这个solve函数比较好理解些，根据height数组的性质，排在i,j之间的子串的最长公共子串为height[i],height[i+1]……height[j]中的最小值所以，只要包含了height[i]<k的子串，其最长公共子串长度必然小于k，由此height[i]<k的位置就形成了一个个的断点考虑lcp的时候只需要考虑断点分隔出的区间里的两两组合就可以了而根据题意，若two==0，，则所有的串都为第一个字符串的子串，自然不存在可比性而就算two>1，那么其中一个必然是另一个的子串，只需要最长的那一个就行了 72 int solve(int kk, int n) 73 { 74int res = 0; 75for (int i = 0; i <= len; i++) 76{ 77if (lcp[i] >= kk) 78{ 79int one = 0, two = 0; 80if (sa[i-1] < n) 81one++; 82if (sa[i-1] > n) 83two++; 84for (; i < len && lcp[i] >= kk; i++) 85{ 86if (sa[i] < n) 87one++; 88if (sa[i] > n) 89two++; 90} 91if (two) 92res += one; 93} 94} 95return res; 96 }*/
快忘了那些不高兴的事吧!你看就连今天的阳光都如此明媚灿烂，
