找相同字符 ([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;
}
分类: 文章

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注