欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4566: [Haoi2016]找相同字符(后缀自动机)

程序员文章站 2022-04-24 22:38:07
题意 "题目链接" Sol 直接在SAM上乱搞 枚举前缀,用SAM统计可以匹配的后缀,具体在匹配的时候维护和当前节点能匹配的最大值 然后再把parent树上的点的贡献也统计上,~~这部分可以爆跳parent树~~(假的,因为这题数据随机),也可以直接树形dp一波记下每个点被统计的次数 cpp inc ......

题意

题目链接

sol

直接在sam上乱搞

枚举前缀,用sam统计可以匹配的后缀,具体在匹配的时候维护和当前节点能匹配的最大值

然后再把parent树上的点的贡献也统计上,这部分可以爆跳parent树(假的,因为这题数据随机),也可以直接树形dp一波记下每个点被统计的次数

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn = 4e5 + 10;
int n1, n2;
char a[maxn], b[maxn];
// struct sam {
    int fa[maxn], ch[maxn][26], len[maxn], siz[maxn], tot, las, root, f[maxn], g[maxn];
    vector<int> v[maxn];
    // sam() {
        // root = las = tot = 1;
    // }
    void insert(int x) {
        int now = ++tot, pre = las; las = now; siz[now] = 1;
        len[now] = len[pre] + 1;
        for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;
        if(!pre) fa[now] = root;
        else {
            int q = ch[pre][x];
            if(len[pre] + 1 == len[q]) fa[now] = q;
            else {
                int ns = ++tot; fa[ns] = fa[q]; len[ns] = len[pre] + 1;
                memcpy(ch[ns], ch[q], sizeof(ch[q]));
                fa[q] = fa[now] = ns;
                for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = ns;
            }
        }
    }
    void build() {
        for(int i = 2; i <= tot; i++) v[fa[i]].push_back(i);
    }
    void dfs(int x, int opt) {
        for(int i = 0; i < v[x].size(); i++) {
            int to = v[x][i];
            dfs(to, opt); 
            if(opt == 1) siz[x] += siz[to]; 
            if(opt == 2) f[x] += f[to] + g[to];
        }
    }
// }sam;
int main() {
    root = las = tot = 1;
    scanf("%s%s", a + 1, b + 1);
    n1 = strlen(a + 1); n2 = strlen(b + 1);
    for(int i = 1; i <= n1; i++) insert(a[i] - 'a');
    build(); dfs(root, 1);
    int now = root, cur = 0; ll ans = 0;
    for(int i = 1; i <= n2; i++) {
        int x = b[i] - 'a';
        if(ch[now][x]) now = ch[now][x], cur++;
        else {
            while(!ch[now][x] && now) now = fa[now];
            if(!now) now = 1, cur = 0;
            else cur = len[now] + 1, now = ch[now][x];
        }
        ans += 1ll * (cur - len[fa[now]]) * siz[now];
        g[now]++;
        //int tmp = fa[now];
        //while(tmp != 1) ans += (len[tmp] - len[fa[tmp]]) * siz[tmp], tmp = fa[tmp];
    }
    dfs(root, 2);
    for(int i = 1; i <= tot; i++) ans += 1ll * (len[i] - len[fa[i]]) * siz[i] * f[i];
    cout << ans;
    return 0;
}
/*
aa
aa

acb
abc

ababababba
abbababab
*/