BZOJ4566: [Haoi2016]找相同字符
Description
Input
两行，两个字符串s1，s2，长度分别为n1，n2。
1 <=n1, n2<= 200000，字符串中只有小写字母
Output
输出一个整数表示答案
Sample Input
bbaa
Sample Output
题解Here!
$O(n^3)$的大暴力：
首先，我们知道。如果连个串中各取一个极长的相同的子串（极长的意思就是这两个串再向两边延伸就会不同或出界），则这个极长的串的所有子串也是相同的。
由于枚举极长的串并求出其长度并不方便，所以我们可以枚举这个极长的串的左端点，再求出其长度。
这样就可以不重不漏找出所有的极长的串。
更图方便的话，我们可以只考虑两原串中某后缀的所有前缀，这可以补充不漏找出所有的子串。
但是由于我们要在两个字符串中枚举，同时找出子串的长度也是$O(n)$的，于是总复杂度为$O(n^3)$。
$O(n^2)$的优化大暴力：
刚才说道了后缀的前缀，我们不由自主想到了后缀数组。
如果我们可以很快求出$A$串和$B$串的某两个后缀的最长公共前缀，我们就可以将时间复杂度优化的更低。
这不就是$height$数组解决的嘛！
所以我们可以将两个字符串通过一个分隔符拼接起来，求出$height$数组，即按字典序排序后每个后缀和前一个的$LCP$。
再利用$height$数组和$ST$表，我们就可以$O(1)$得到任意两后缀的$LCP$。
因此，这样做的时间复杂度只有枚举子串起点的复杂度了，即$O(n^2)$。
$O(nlog_2n)$的正解：
现在拉高时间复杂度的罪魁祸首就是枚举起点了。
所以我们想将其复杂度降低。
考虑到利用$height$数组求任意两个后缀的$LCP$时的独特性质：
两个后缀的$LCP$为字典序排序后他们中间夹的最小的$height$。
也就是说排序后，一个后缀越往后数$LCP$的长度越小。
这样，我们就可以用单调栈维护这个最小值。
分$A$串的子串在前、$B$的子串在前两种情况分别用单调栈求出答案，加起来就行。
至于如何维护，emmm......
由于利用了单调栈这个神奇的手段,时间复杂度降到了$O(nlog_2n)$，也就是倍增处理后缀数组的复杂度。
当然你可以用$DC3$来完成，复杂度可以降到$O(n)$。（当然，本蒟蒻不会啦。。。）
附代码：
#include
#include
#include
#include
#define MAXN 400010
using namespace std;
pair stack[MAXN];
int n,l1,l2;
int val[MAXN],sum[MAXN];
char str[MAXN];
int top,sa[MAXN],rk[MAXN],tax[MAXN],tp[MAXN],height[MAXN];
inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w;
}
void radixsort(){for(int i=0;i<=top;i++)tax[i]=0;for(int i=1;i<=n;i++)tax[rk[i]]++;for(int i=1;i<=top;i++)tax[i]+=tax[i-1];for(int i=n;i>=1;i--)sa[tax[rk[tp[i]]]--]=tp[i];
}
void suffixsort(){top=30;for(int i=1;i<=n;i++){rk[i]=val[i];tp[i]=i;}radixsort();for(int w=1,p=0;pw)tp[++p]=sa[i]-w;radixsort();swap(tp,rk);rk[sa[1]]=p=1;for(int i=2;i<=n;i++)rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;}
}
void getheight(){for(int i=1,j,k=0;i<=n;i++){if(k)k--;j=sa[rk[i]-1];while(val[i+k]==val[j+k])k++;height[rk[i]]=k;}
}
void work(){long long ans=0;top=0;stack[0]=make_pair(1,0);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(sa[i]<=l1);for(int i=1;i<=n;i++){while(top&&height[i]l1+1)ans+=stack[top].second;}top=0;for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(sa[i]>l1+1);for(int i=1;i<=n;i++){while(top&&height[i] 以上是后缀数组解法，当然你可以用$SAM$吊打$SA$，就像$AC$自动机吊打$Trie$和$KMP$一样。。。
（坑，未填。。。）