? ? ? 顯然我們可以先把len(Ti)+len(Tj)的值先算出來，再把LCP減去。所有l(wèi)en(Ti)+len(Tj)的值為n*(n-1)*(n+1)/2，這個(gè)隨便在紙上畫一畫就可以算出來的。

? ? ??接下來問題就是如何把LCP減去。我們先用后綴數(shù)組把height求出來，當(dāng)有一段區(qū)間l~r，height[i]為height[l]~height[r]中的最小值，那么隨便取rk[l]~rk[r]中的兩個(gè)后綴，他們的LCP則都是height[i]，這個(gè)很好理解吧。那么l~r這個(gè)區(qū)間里有(l-i+1)*(r-i+1)對后綴，所以我們最后的答案就要減去2*height[i]*(l-i+1)*(r-i+1)【1≤i≤n】。

? ? ? 然后就是如何求出每一個(gè)i的l~r了，暴力枚舉+RMQ顯然不行，那我們就用一個(gè)單調(diào)棧，棧里存著i前面height值比height[i]小的height值的編號，記為j，如果height[j]比height[i]大那么就彈出，那么這段區(qū)間的左端點(diǎn)則為棧頂?shù)膉+1，右端點(diǎn)同理。這樣我們就可以求出每個(gè)height的l和r了。

奇丑無比的代碼如下：

vars:ansistring;i:longint;n,m,l,r,ans,top:int64;rk,trk,sa,tsa,sum,h,ll,rr,st:array[0..500005]of int64;procedure suffix; vari,j,p:longint; beginfor i:=1 to n do begin trk[i]:=ord(s[i]);inc(sum[trk[i]]);end;for i:=2 to 255 do inc(sum[i],sum[i-1]);for i:=n downto 1 do begin sa[sum[trk[i]]]:=i;dec(sum[trk[i]]);end;rk[sa[1]]:=1;p:=1;for i:=2 to n do begin if trk[sa[i]]<>trk[sa[i-1]] then inc(p);rk[sa[i]]:=p;end;m:=p;j:=1;while m<n dobeginmove(rk,trk,sizeof(rk));fillchar(sum,sizeof(sum),0);p:=0;for i:=n-j+1 to n do begin inc(p);tsa[p]:=i;end;for i:=1 to n do if sa[i]>j then begin inc(p);tsa[p]:=sa[i]-j;end;for i:=1 to n do begin rk[i]:=trk[tsa[i]];inc(sum[rk[i]]);end;for i:=2 to n do inc(sum[i],sum[i-1]);for i:=n downto 1 do begin sa[sum[rk[i]]]:=tsa[i];dec(sum[rk[i]]);end;rk[sa[1]]:=1;p:=1;for i:=2 to n dobeginif (trk[sa[i]]<>trk[sa[i-1]])or(trk[sa[i]+j]<>trk[sa[i-1]+j])then inc(p);rk[sa[i]]:=p;end;m:=p;j:=j*2;end;h[1]:=0;p:=0;for i:=1 to n dobeginif rk[i]=1 then continue;j:=sa[rk[i]-1];while s[i+p]=s[j+p] do inc(p);h[rk[i]]:=p;if p>0 then dec(p);end; end;beginreadln(s);n:=length(s);s:=s+' ';suffix;ans:=n*(n-1)*(n+1)div 2;h[0]:=-maxlongint;for i:=1 to n dobeginwhile h[i]<=h[st[top]] do dec(top);if st[top]=0 then ll[i]:=1else ll[i]:=st[top]+1;inc(top);st[top]:=i;end;h[n+1]:=-maxlongint;top:=0;st[0]:=n+1;for i:=n downto 0 dobeginwhile h[i]<h[st[top]] do dec(top);if st[top]=n+1 then rr[i]:=nelse rr[i]:=st[top]-1;inc(top);st[top]:=i;end;for i:=1 to n doans:=ans-2*(i-ll[i]+1)*(rr[i]-i+1)*h[i];writeln(ans); end. View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Sakits/p/5351175.html

總結(jié)

以上是生活随笔為你收集整理的[bzoj3238]差异（后缀数组+单调栈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。