The Preliminary Contest for ICPC Asia Xuzhou 2019 G.Colorful String PAM(回文自动机) + 可持久化线段树
字符串 可持久化线段树   发布于 2019-09-11   525人围观  0条评论
字符串 可持久化线段树   发表于 2019-09-11   525人围观  0条评论

题目大意

给出一个字符串,求出所有回文串的字符种类数之和。

题解

考场上他们都有回文自动机的板子而我没有QAQ

首先对于一个子串,其对应一个子区间,这个子区间的数据的种类数的多少我们是可以用主席树来维护的,这是众所周知的。

具体维护方法:

从第1位置往后扫,如果之前出现过相同的数据,我们就在之前出现过的位置-1,在当前位置计数+1,然后把当前位置记录下来。

但是我们怎么求所有回文串的长度和数目?Manacher是不行的,效率太低了。

于是有一个神奇的PAM,也就是回文自动机。

回文自动机中,cnt[i]表示以i结尾的最长的回文串的数目,len[i]表示以i结尾的回文串的长度为多少,pos[i]表示以i为结尾的回文串在原串的位置是哪里。

这样的PAM的时间复杂度是O(n*log(字符集大小))的

这样我们就很容易能够求得答案了。

最终答案是ans = n + Σ query(root[pos[i]],1,siz,pos[i]-len[i]+1,pos[i]) * cnt[i];

据说还有后缀自动机SAM的做法,这个我也不怎么会……所以就不写了,等以后学QAQ。

如果对回文自动机不了解的可以去找博客https://www.cnblogs.com/nbwzyzngyl/p/8260921.html

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
typedef long long ll;
struct seg{
    int ch[2];
    int val;
}tr[maxn*25];
int root[maxn];
char s[maxn];
int siz = 0;
struct PAM{
    int p,last,cur,n,S[maxn],len[maxn],pos[maxn],cnt[maxn],fail[maxn];
    int nt[maxn][26];
    int new_node(int l){
        for(int i = 0;i < 26;++i)
            nt[p][i] = 0;
        len[p] = l;
        cnt[p] = 0;
        return p++;
    }
    inline void init(){
        p = n = last = 0;
        new_node(0);
        new_node(-1);
        S[0] = -1;fail[0] = 1;
        return;
    }
    int get_fail(int x){
        while(S[n - len[x] - 1] != S[n])
            x = fail[x];
        return x;
    }
    inline void add(char c,int post){
//        c -= 'a';
        S[++n] = c;
        int cur = get_fail(last);
        if(!nt[cur][c]){
            int now = new_node(len[cur]+2);
            if(len[now] > 1)pos[now] = post;
            fail[now] = nt[get_fail(fail[cur])][c];
            nt[cur][c] = now;
        }
        last = nt[cur][c];
        cnt[last]++;
        return;
    }
    void count(){
        for(int i = p-1;i >= 0;--i)
            cnt[fail[i]] += cnt[i];
        return;
    }
}run;
int cnt = 0;
int build(int l,int r){
    int now = ++cnt;
    tr[now].val = tr[now].ch[0] = tr[now].ch[1] = 0;
    if(l == r)
        return now;
    int mid = (l + r) >> 1;
    tr[now].ch[0] = build(l,mid);
    tr[now].ch[1] = build(mid+1,r);
    return now;
}
int update(int pre,int l,int r,int pos,int val){
    int now = ++cnt;
    tr[now] = tr[pre];
    tr[now].val += val;
    if(l == r)
        return now;
    int mid = (l + r) >> 1;
    if(pos <= mid)
        tr[now].ch[0] = update(tr[pre].ch[0],l,mid,pos,val);
    else if(pos > mid)
        tr[now].ch[1] = update(tr[pre].ch[1],mid+1,r,pos,val);
    return now;
}
int query(int now,int l,int r,int ql,int qr){
    if(l >= ql && r <= qr)
        return tr[now].val;
    int mid = (l + r) >> 1;
    int ans = 0;
    if(ql <= mid)
        ans += query(tr[now].ch[0],l,mid,ql,qr);
    if(qr > mid)
        ans += query(tr[now].ch[1],mid+1,r,ql,qr);
    return ans;
}
int pf[maxn];
int main(){
    scanf("%s",s+1);
    siz = strlen(s+1);
    memset(pf,0,sizeof(pf));
    for(int i = 1;i <= siz;++i)
        s[i] -= 'a';
    root[0] = build(1,siz);
    for(int i = 1;i <= siz;++i){
        root[i] = update(root[i-1],1,siz,i,1);
        if(pf[s[i]])root[i] = update(root[i],1,siz,pf[s[i]],-1);
        pf[s[i]] = i;
    }
    run.init();
    for(int i = 1;i <= siz;++i)
        run.add(s[i],i);
    run.count();
    ll ans = siz;
    for(int i = 2;i < run.p;++i){
        if(run.len[i] > 1)
            ans += (ll)query(root[run.pos[i]],1,siz,run.pos[i] - run.len[i] + 1,run.pos[i]) * (ll)run.cnt[i];
    }
    printf("%lld\n",ans);
    return 0;
}

 

上一篇: HDU 6209 The Intersection 分数二分

下一篇: The 2019 Asia Nanchang First Round Online Programming Contest A.Enju With math problem 思维题 欧拉筛

立即登录,发表评论
没有帐号?立即注册
0 条评论