Qiuly

「AHOI2013」差异 后缀自动机.SAM luoguP4248
刚开始发现 $SA$ 很可做,不过当时没有看范围,心想美滋滋了这个就是 $SA$ 的板子,然后一看范围心就凉了。不...
扫描右侧二维码阅读全文
22
2019/05

「AHOI2013」差异 后缀自动机.SAM luoguP4248

刚开始发现 $SA$ 很可做,不过当时没有看范围,心想美滋滋了这个就是 $SA$ 的板子,然后一看范围心就凉了。

不过可以用 $SAM$ ,我们知道,对于两个串,它们的最长公共子串就是它们在前缀树上的 $Lca$ 。这是显然的,不明白的同学可以康康 $Qiuly$ 酱之前写的 $SAM$ ,可以观察观察图片。

我们观察式子,发现 $\sum_{1\leq i<j\leq n} len(T_i)+len(T_j)$ 是等于 $\frac{(n-1)\times n\times(n+1)}{2}$ 的,这个可以 $O(1)$ 算出。

那么 $2\times lcp(T_i,T_j)$ 怎么求呢?

那么对于一个结点 $x$ ,我们依次统计 $x$ 的儿子,并依次更新 $x$ 的 $size$ ,对于一个 $x$ 的儿子 $y$ ,枚举的时候它对答案的贡献显然是 $size[x]\times len[x]\times size[y]$ ,因为 $y$ 的子树中的任意一结点(包括 $y$ ) ,与 $x$ 之前枚举过的所有儿子的子树中的所有结点的 $Lca$ 都是 $x$ 。并且对于一个 $x$ ,它所造成的贡献就是 $Len[x]$ 。

最后统计出来的答案再乘上 $2$ 就是后面那个式子啦~\(≧▽≦)/~

不过要注意一点,后缀自动机是会复制结点的,这些复制的结点不属于原串因此不能计算贡献。

然后就是代码的问题了。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+7;
struct SAM {
    int last,cnt;
    int ch[N][26],fa[N],len[N],sz[N],hep[N],tot[N];
    SAM() {last=cnt=1;}
    inline void ins(int c) {
        int p=last,np=++cnt;
        last=np,len[np]=len[p]+1,sz[np]=1;
        while(p&&!ch[p][c]) ch[p][c]=np,p=fa[p];
        if(!p)fa[np]=1;
        else {
            int q=ch[p][c];
            if(len[q]==len[p]+1)fa[np]=q;
            else {
                int nq=++cnt;len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[q]=fa[np]=nq;
                while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p];
            }
        }return;
    }
    inline ll calc() {
        ll res=0;
        for(int i=1;i<=cnt;++i) hep[len[i]]++;
        for(int i=1;i<=cnt;++i) hep[i]+=hep[i-1];
        for(int i=1;i<=cnt;++i) tot[hep[len[i]]--]=i;
        for(int i=cnt;i>=1;--i) {
            int node=tot[i];
            res+=(ll)sz[fa[node]]*sz[node]*len[fa[node]];
            sz[fa[node]]+=sz[node];
        }return res;
    }
}T;
char s[N];
int main() {
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;++i)T.ins(s[i]-'a');
    printf("%lld\n",(ll)(n-1)*n*(n+1)/2-2*T.calc());
    return 0;
}
最后修改:2019 年 05 月 30 日 03 : 24 PM

发表评论