题目：http://poj.org/problem?id=3415
因为求 LCP 是后缀数组的 ht[ ] 上的一段取 min ，所以考虑算出 ht[ ] 之后枚举每个位置作为右端的贡献。
一开始想的是把两个数组接起来（中间加个逗号之类的，就能算出正确的 LCP ），不加区分地算了贡献之后再分别减去两个数组自己内部的贡献。
看看题解，得知可以在那个接起来的数组上分别算 a 与前面的 b 、b 与前面的 a 的贡献，就不用容斥了。
考虑怎么算贡献。一开始想的是取 min 一定越取越小，所以维护双指针卡在取min>=K的最靠前位置；新加入一个元素的时候二分找到第一个取min后比自己小的位置，改一下该位置到自己位置的贡献（现在看来好像不用维护那个双指针也行？）；
看看题解，原来可以用单调栈。就相当于维护一下单调栈的“面积”一样。
不过有一点麻烦的是 i 位置能否产生贡献是看 i+1 位置到末尾位置的 min ；这样求“面积”就要费点心；不过想到可以让 ht[ i ] = ht[ i+1 ] ，这样的话正常求面积就行了！累计到答案上之后再把当前位置入队。
注意有大写字母。而且 poj 上编译不过 swap( rk , tp ) ，写 memcpy 就行了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=1e5+5,M=N<<1; int n,m,s[M],sa[M],rk[M],tp[M],tx[M],ht[M]; int sta[M],top,wd1[M],wd2[M]; ll sm1[M],sm2[M]; char a[N],b[N]; int Mx(int a,int b){return a>b?a:b;} void Rsort(int n,int nm) {for(int i=1;i<=nm;i++)tx[i]=0;for(int i=1;i<=n;i++)tx[rk[i]]++;for(int i=2;i<=nm;i++)tx[i]+=tx[i-1];for(int i=n;i;i--)sa[tx[rk[tp[i]]]--]=tp[i]; } void get_sa(int n) {int nm=60;for(int i=1;i<=n;i++)tp[i]=i,rk[i]=s[i];Rsort(n,nm);for(int k=1;k<=n;k<<=1){int tot=0;for(int i=n-k+1;i<=n;i++)tp[++tot]=i;for(int i=1;i<=n;i++)if(sa[i]>k)tp[++tot]=sa[i]-k;Rsort(n,nm);memcpy(tp,rk,sizeof rk);/*swap(rk,tp);*/nm=1;rk[sa[1]]=1;for(int i=2,u,v;i<=n;i++){u=sa[i]+k;v=sa[i-1]+k;if(u>n)u=0;if(v>n)v=0;rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[u]==tp[v])?nm:++nm;}if(nm==n)break;} } void get_ht(int n) {int k=0,j;for(int i=1;i<=n;i++){for(j=sa[rk[i]-1],k?k--:0;i+k<=n&&j+k<=n&&s[i+k]==s[j+k];k++);ht[rk[i]]=k;} } int main() {while(1){int lm;scanf("%d",&lm);if(!lm)return 0;scanf("%s",a+1);scanf("%s",b+1);n=strlen(a+1); m=strlen(b+1); int tn=n+m+1;for(int i=1;i<=n;i++)s[i]=a[i]-'A'+1;s[n+1]=60;for(int i=n+2,j=1;i<=tn;i++,j++)s[i]=b[j]-'A'+1;get_sa(tn);get_ht(tn);for(int i=1;i<tn;i++)ht[i]=ht[i+1];top=0; ll ans=0;for(int i=1;i<=tn;i++){if(sa[i]<=n)ans+=sm2[top]; else if(sa[i]>n+1)ans+=sm1[top];int lj1=0,lj2=0;while(top&&ht[i]<=ht[sta[top]])lj1+=wd1[top],lj2+=wd2[top],top--;sta[++top]=i;if(sa[i]<=n)lj1++; else if(sa[i]>n+1)lj2++;wd1[top]=lj1; sm1[top]=sm1[top-1]+(ll)lj1*Mx(0,ht[i]-lm+1);wd2[top]=lj2; sm2[top]=sm2[top-1]+(ll)lj2*Mx(0,ht[i]-lm+1);}printf("%lld\n",ans);}return 0; }