找相同字符 ([HAOI2016、luogu3181)

题意：

? 给定两个由小写字母组成的字符串 s1,s2(长度小于等于 $2\times 10^4$)。求两个字符串各取一个子串，两子串相等的方案数。

分析:

$$O(n^3)$$:

? 首先，我们知道。如果连个串中各取一个极长的相同的子串 (极长的意思就是这两个串再向两边延伸就会不同或出界)，则这个极长的串的所有子串也是相同的。

? 由于枚举极长的串并求出其长度并不方便，所以我们可以枚举这个极长的串的左端点，再求出其长度。这样就可以不重不漏找出所有的极长的串。更图方便的话，我们可以只考虑两原串中某后缀的所有前缀，这可以补充不漏找出所有的子串。但是由于我们要在两个字符串中枚举，同时找出子串的长度也要话费 $O(n)$的代价，固总时间复杂度是 $O(n^3)$的。

$$O(n^2)$$:

? 刚才说道了后缀的前缀，我们不由自主想到了后缀数组。如果我们可以很快求出 A 串和 B 串的某两个后缀的最长公共前缀，我们就可以将时间复杂度优化的更低。所以我们可以将两个字符串通过一个分隔符拼接起来，求出 Height 数组，即按字典序排序后每个后缀和前一个的 LCP。再利用 Height 数组和 ST 表，我们就可以 $O(1)$得到任意两后缀的 LCP。因此，这样做的时间复杂度只有枚举子串起点的复杂度了，即 $O(n^2)$。

$$O(nlogn)$$:

? 现在拉高时间复杂度的罪魁祸首就是枚举起点了。所以我们想将其复杂度降低。考虑到利用 Height 数组求任意两个后缀的 LCP 时的独特性质：两个后缀的 LCP 为字典序排序后他们中间夹的最小的 Height。也就是说排序后，一个后缀越往后数 LCP 的长度越小。

? 这样，我们就可以用单调栈维护这个最小值。分 A 串的子串在前、B 的子串在前两种情况分别用单调栈求出答案，加起来就行。至于如何维护，聪明的大家一定已经知道了。

? 由于利用了单调栈这个神奇的手段, 时间复杂度降到了 $O(nlogn)$。如果我们在构建后缀数组的时候采用 DC3 算法，我们甚至可以在线性时间内解决这道题。

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <cstdio>
#define MX 823123

using namespace std;
typedef long long ll;
typedef struct tSA
{
    int str[MX],n,m;
    int rank[MX],SA[MX],het[MX];
    int buk[MX],yp[MX];
    bool cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
    void jsort()
    {
        for(int i=0;i<=m;i++)buk[i]=0;
        for(int i=1;i<=n;i++)buk[rank[yp[i]]]++;
        for(int i=1;i<=m;i++)buk[i]+=buk[i-1];
        for(int i=n;i>=1;i--)SA[buk[rank[yp[i]]]--]=yp[i];
    }
    void getSA()
    {
        for(int i=1;i<=n;i++)rank[i]=str[i],yp[i]=i;
        m=28;jsort();
        for(int w=1;w<n;w<<=1)
        {
            int p=0;
            for(int i=n-w+1;i<=n;i++)yp[++p]=i;
            for(int i=1;i<=n;i++)if(SA[i]>w)yp[++p]=SA[i]-w;
            jsort(),swap(rank,yp),rank[SA[1]]=p=1;
            for(int i=2;i<=n;i++)rank[SA[i]]=(cmp(yp,SA[i],SA[i-1],w)?p:++p);
            m=p;
        }
        int k=0;
        for(int i=1;i<=n;i++)
        {
            k=(k?k-1:0);
            while(str[i+k]==str[SA[rank[i]-1]+k])k++;
            het[rank[i]]=k;
        }
    }
}SA;
SA sa;
char str[MX];
int l1,l2,top,sum[MX];
pair<int,ll>stk[MX];
void work()
{
    ll ans=0;
    stk[0]=make_pair(1,0);
    for(int i=1;i<=sa.n;i++)sum[i]=sum[i-1]+(sa.SA[i]<=l1);
    for(int i=1;i<=sa.n;i++)
    {
        while(top&&sa.het[stk[top].first]>sa.het[i])top--;
        top++;
        stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*sa.het[i]+stk[top-1].second);
        if(sa.SA[i]>l1+1)ans+=stk[top].second;
    }
    top=0;
    for(int i=1;i<=sa.n;i++)sum[i]=sum[i-1]+(sa.SA[i]>l1+1);
    for(int i=1;i<=sa.n;i++)
    {
        while(top&&sa.het[stk[top].first]>sa.het[i])top--;
        top++;
        stk[top]=make_pair(i,(sum[i-1]-sum[stk[top-1].first-1])*sa.het[i]+stk[top-1].second);
        if(sa.SA[i]<=l1)ans+=stk[top].second;
    }
    printf("%lld\n",ans);
}
int main()
{
    scanf("%s",str+1);l1=strlen(str+1);
    scanf("%s",str+l1+2);
    str[l1+1]='z'+1;
    sa.n=strlen(str+1);
    for(int i=1;i<=sa.n;i++)sa.str[i]=str[i]-'a'+1;
    sa.getSA();
    work();
    return 0;
}