洛谷 P4248 / loj 2377 [AHOI2013] 差异题解【后缀自动机】【树形DP】

可能是一个 SAM 常用技巧？感觉 SAM 的基础题好多啊..

题目描述

给定一个长度为 \(n\) 的字符串 \(S\) ，令 \(T_i\) 表示它从第 \(i\) 个字符开始的后缀，求：

\[\sum_{1\le i<j\le n}len(T_i)+len(T_j)-2\times lcp(T_i,T_j)
\]

其中，\(len(a)\) 表示字符串 \(a\) 的长度，\(lcp(a,b)\) 表示字符串 \(a\) 和字符串 \(b\) 的最长公共前缀。

输入输出格式

输入格式：

一行，一个字符串 \(S\)。

输出格式：

一行，一个整数，表示所求值。

输入输出样例

输入样例：
ababc
输出样例：
54
数据范围与约定

对于 \(100\%\) 的数据，保证 \(2\le n\le 500000\)，且均为小写字母。

题解：

这个题的主要考点是 SAM 求 lcp。

lcp 是最长公共前缀，而我们用的是后缀自动机。只需要把字符串翻转过来建立 SAM，得到的就是”前缀自动机“了。

类似后缀自动机的性质，我们建造 parent 树，则父亲总是儿子的前缀。而最简状态自动机上的每个点都有自己的 \(mn,mx\) 表示同一个 Right 集合能表示的最短和最长子串，因此任意两个状态的 lcp 长度就是它们在 parent 树上的最近公共祖先节点的 \(mx\)。

然后我们只需要计算任意两点的 lcp 即可，这个操作可以一次 dfs 搞定。注意统计时子树的根也要算上。

每个点做出的贡献是它的 Right 集合大小，可以通过在 parent 树上统计子树信息得到。

此外，前面的 \(\sum_{1\le i<j\le n}i+j\) 可以推导出来 \(O(n)\) 或 \(O(1)\) 求出来。

时间复杂度 \(O(n)\)。

Code：

#include<cstdio>

#include<cstring>

#include<algorithm>

struct edge

{

    int n,nxt;

    edge(int n,int nxt)

    {

        this->n=n;

        this->nxt=nxt;

    }

    edge(){}

}e[1000100];

int head[1000100],ecnt=-1;

void add(int from,int to)

{

    e[++ecnt]=edge(to,head[from]);

    head[from]=ecnt;

}

int n;

char s[500100];

int ch[26][1000100],mx[1000100],r[1000100],par[1000100],pcnt;

void build()

{

    int p=pcnt=1;

    for(int i=1;i<=n;++i)

    {

        int w=s[i]-'a';

        int np=++pcnt;

        mx[np]=mx[p]+1;

        r[np]=1;

        while(p&&!ch[w][p])

        {

            ch[w][p]=np;

            p=par[p];

        }

        if(!p)

            par[np]=1;

        else

        {

            int q=ch[w][p];

            if(mx[q]==mx[p]+1)

                par[np]=q;

            else

            {

                int nq=++pcnt;

                mx[nq]=mx[p]+1;

                while(p&&ch[w][p]==q)

                {

                    ch[w][p]=nq;

                    p=par[p];

                }

                for(int j=0;j<26;++j)

                    ch[j][nq]=ch[j][q];

                par[nq]=par[q];

                par[q]=nq;

                par[np]=nq;

            }

        }

        p=np;

    }

}

long long ans=0;

void dfs(int x)

{

    long long tmp=r[x];

    for(int i=head[x];~i;i=e[i].nxt)

    {

        dfs(e[i].n);

        ans-=tmp*mx[x]*r[e[i].n]*2;

        r[x]+=r[e[i].n];

        tmp+=r[e[i].n];

    }

}

int main()

{

    memset(head,-1,sizeof(head));

    scanf("%s",s+1);

    n=strlen(s+1);

    for(int i=1;i<=n;++i)

        ans+=3ll*i*(i-1);

    ans>>=1;

    std::reverse(s+1,s+1+n);

    build();

    for(int i=2;i<=pcnt;++i)

        add(par[i],i);

    dfs(1);

    printf("%lld\n",ans);

    return 0;

}

巴特西

洛谷 P4248 / loj 2377 [AHOI2013] 差异题解【后缀自动机】【树形DP】

题目描述

输入输出格式

输入输出样例

数据范围与约定

题解：

Code：

最新文章

热门文章

巴特西

洛谷 P4248 / loj 2377 [AHOI2013] 差异 题解【后缀自动机】【树形DP】

题目描述

输入输出格式

输入输出样例

数据范围与约定

题解：

Code：

最新文章

热门文章

洛谷 P4248 / loj 2377 [AHOI2013] 差异题解【后缀自动机】【树形DP】