原題走這里

鑒于我實在不是很懂單調(diào)棧和單調(diào)隊列這一系列東西，所以我決定稍微具體講一下單調(diào)棧。

恩，本題實質(zhì)上就是求兩個字符串的公共子串數(shù)，其中只要出現(xiàn)位置不同，就算是不同的子串。
處理多個字符串的經(jīng)典套路：把兩個字符串連在一起，中間用分割符分割。
于是問題就轉(zhuǎn)化為了：求分隔符前后都出現(xiàn)過的子串個數(shù)。
子串就是后綴的前綴，于是問題又轉(zhuǎn)化成了：求整個串中，任意兩個后綴的LCP之和，這兩個子串要一個在分割符前，一個在分割符后。

恩，求后綴的LCP我們可以用后綴數(shù)組中的height數(shù)組，兩個后綴的LCP長度就是height上的區(qū)間最小值。
于是我們要求的實際上就是：

∑SA[i]<n+1<SA[j]mini≤k≤jheight[k]+∑SA[j]<n+1<SA[i]mini≤k≤jheight[k] ∑ S A [ i ] < n + 1 < S A [ j ] min i ≤ k ≤ j h e i g h t [ k ] + ∑ S A [ j ] < n + 1 < S A [ i ] min i ≤ k ≤ j h e i g h t [ k ]

其中SA是排名第 i i 的后綴的編號。
讓我們姑且只考慮左邊，一個明顯的暴力解法是枚舉i,ji,j然后RMQ求出區(qū)間最小值。
然而這個解法明顯不符合時間復(fù)雜度的要求，因此我們的方法有待改進。

首先我們發(fā)現(xiàn)，右端點固定的一系列區(qū)間最小值，能夠構(gòu)成一個單調(diào)增的序列，其中相同的值可以合并。
如果我們不斷將右端點右移，則序列末端的一些值會被更新為同一個值，可以將這幾個值合并，相當于這幾個值被從隊列末端彈掉了。
與此同時如果你又掃到了某一個 SA[i]<n+1 S A [ i ] < n + 1 的 i i ，你又要把它加進序列的末端。
這相當于一個棧的結(jié)構(gòu)，而其中的元素又是單調(diào)的，就是所謂的單調(diào)棧。

于是，我們可以使用單調(diào)棧，求出式子的值即可，時間復(fù)雜度為O(n)O(n)，加上構(gòu)造后綴數(shù)組，共 O(nlogn) O ( n l o g n ) 。

諸君，我討厭單調(diào)棧。

講真，一開始，我的解法是二分，然后二分合并左右兩邊結(jié)果的時候用的又是單調(diào)棧，然后還AC了，后來看題解才發(fā)現(xiàn)，只用單調(diào)棧就可以了。

具體詳見代碼如下：

// luogu-judger-enable-o2 #include <bits/stdc++.h> #define LL long long using namespace std; int n,len,SA[400010],r[400010],tp[400010],t[400010],h[400010],st[400010],s[400010],top; char ch[400010]; void Sort(int m) {memset(t,0,sizeof(int)*(m+1));for(int i=1; i<=len; i++) {t[r[i]]++;}for(int i=1; i<=m; i++) {t[i]+=t[i-1];}for(int i=len; i; i--) {SA[t[r[tp[i]]]--]=tp[i];} } void build_SA() {Sort(127);for(int i=1,p=0,m=127; i<=len&&p<len; i<<=1,m=p) {p=0; for(int j=len-i+1; j<=len; j++) {tp[++p]=j;}for(int j=1; j<=len; j++) {if(SA[j]>i) {tp[++p]=SA[j]-i;}}Sort(m);swap(r,tp);r[SA[1]]=p=1;for(int j=2; j<=len; j++) {r[SA[j]]=((tp[SA[j]]==tp[SA[j-1]])&&(tp[SA[j]+i]==tp[SA[j-1]+i])?p:++p);}}for(int i=1,j,k=0; i<=len; h[r[i++]]=k) {for(k?k--:0,j=SA[r[i]-1]; ch[i+k]==ch[j+k]; k++);} } LL solve(bool b) {LL ret=0,temp=0;top=0; for(int i=len,j=0; i; i--,j=0) {if((SA[i]>n)^b){ret+=temp;}while(st[top]>h[i]&&top){temp-=1LL*s[top]*st[top];j+=s[top--];}st[++top]=h[i];s[top]=j;if((SA[i]<=n)^b) { //向單調(diào)棧內(nèi)插入元素s[top]++;} temp+=1LL*s[top]*st[top];}return ret; } int main() {scanf("%s",ch+1);n=strlen(ch+1);ch[n+1]='$';scanf("%s",ch+n+2);len=strlen(ch+1);for(int i=1;i<=len;i++){tp[i]=i;r[i]=ch[i];}build_SA();cout<<solve(0)+solve(1)<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【HAOI2016/BZOJ4566】找相同字符 后缀数组+单调栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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