M_sea

洛谷2408 不同子串个数
Luogu分析如果要用 $\mathrm{SA}$ 的话,答案就是 $\sum\limits_{i=1}^n n-...
扫描右侧二维码阅读全文
23
2019/03

洛谷2408 不同子串个数

Luogu

分析

如果要用 $\mathrm{SA}$ 的话,答案就是 $\sum\limits_{i=1}^n n-sa[i]-height[i]$ 。

不过 $\mathrm{SAM}$ 也可以做。

发现 $\mathrm{SAM}$ 上的每条路径都代表一个子串,然后 $\mathrm{SAM}$ 又是一个 $\mathrm{DAG}$ ,所以可以 $\mathrm{DP}$ 。

设 $f[i]$ 表示从节点 $i$ 出发的路径数,显然有 $f[i]=\sum\limits_{v\in son_i} (f[v]+1)$ 。

具体实现及细节见代码。

代码

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

const int N=200000+10;

int n;
char s[N];

int last,cnt;
int ch[N<<1][26],fa[N<<1],len[N<<1];
    
inline void extend(int c) {
    int p=last,np=++cnt; last=np,len[np]=len[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(len[p]+1==len[q]) 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;
            for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}

inline void build() {
    last=cnt=1;
    for (re int i=1;i<=n;++i) extend(s[i]-'a');
}

int a[N],b[N];
ll f[N];

int main() {
    scanf("%d%s",&n,s+1);
    build();
    for (re int i=1;i<=cnt;++i) ++b[len[i]];
    for (re int i=1;i<=cnt;++i) b[i]+=b[i-1];
    for (re int i=1;i<=cnt;++i) a[b[len[i]]--]=i;
    for (re int i=cnt;~i;--i) {
        int p=a[i];
        for (re int j=0;j<26;++j)
            if (ch[p][j]) f[p]+=f[ch[p][j]]+1;
    }
    printf("%lld\n",f[1]);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 19 PM

发表评论