M_sea

洛谷4248 [AHOI2013]差异
LuoguBZOJ分析题目中的式子$\mathrm{len(T_i)+len(T_j)-2\times lcp(T...
扫描右侧二维码阅读全文
25
2018/12

洛谷4248 [AHOI2013]差异

Luogu

BZOJ

分析

题目中的式子$\mathrm{len(T_i)+len(T_j)-2\times lcp(T_i,T_j)}$,可以看做$\mathrm{parent}$树上的$i$到$j$的路径长。

定义以$p$为儿子的路径的边权为$l[p]-l[fa[p]]$,然后就变成了求所有后缀之间的路径的长度和。

显然,对于这条边,它被$size[p]\times (len-size[p])$路径经过。然后把这个东西乘上边权累加即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000+10;

char s[MAXN];
int len;

struct Suffix_Automaton {
    int last,cnt;
    int ch[MAXN<<1][26],fa[MAXN],l[MAXN],sz[MAXN];
    inline void ins(int c) {
        int p=last,np=++cnt; last=np,l[np]=l[p]+1;
        for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
        if (!p) fa[np]=1;
        else {
            int q=ch[p][c];
            if (l[p]+1==l[q]) fa[np]=q;
            else {
                int nq=++cnt; l[nq]=l[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[q]=fa[np]=nq;
                for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
        sz[np]=1;
    }
    inline void build() {
        last=cnt=1;
        for (re int i=1;i<=len;++i) ins(s[i]-'a');
    }
    int a[MAXN],c[MAXN];
    inline void solve() {
        long long ans=0;
        for (re int i=1;i<=cnt;++i) ++c[l[i]];
        for (re int i=1;i<=cnt;++i) c[i]+=c[i-1];
        for (re int i=1;i<=cnt;++i) a[c[l[i]]--]=i;
        for (re int i=cnt;i>=1;--i) {
            int p=a[i];
            sz[fa[p]]+=sz[p];
            ans+=1ll*(l[p]-l[fa[p]])*sz[p]*(len-sz[p]);
        }
        printf("%lld\n",ans);
    }
} SAM;

int main() {
    scanf("%s",s+1); len=strlen(s+1);
    SAM.build();
    SAM.solve();
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 49 PM

4 条评论

  1. xzz小蒟蒻

    Orz M_sea

    1. M_sea
      @xzz小蒟蒻

      Orz xzz

  2. xgzc

    Orz,你就会SAM了

    1. M_sea
      @xgzc

      您早就会了qwq

发表评论