URAL – 1960 Palindromes and Super Abilities 回文自动机

Palindromes and Super Abilities 回文自动机

 Source

URAL - 1960

My Solution

题意：逐个字符的添加一个字符串，问每添加一个字符显存的字符串的总不同的回文子串的个数。

回文树自动机

首先推荐篇比较好的讲回文自动机即回文树的博客，

Palindromic Tree——回文树【处理一类回文串问题的强力工具】

按照功能翻译是回文自动机，按照自字面翻译是回文树。

然后这题把Palindromic_Machine里原来的void add成员函数，改成在出现新的回文子串的时候(!nxt[cur][c])返回1否则返回0即可。

复杂度 O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;
const int CHAR_SIZE = 26;

struct Palindromic_Machine{
    int nxt[MAXN][CHAR_SIZE], fail[MAXN];
    int cnt[MAXN], num[MAXN], len[MAXN], S[MAXN];
    int last, n, p;
    int newnode(int l){
        for(int i = 0; i < CHAR_SIZE; i++) nxt[p][i] = 0; cnt[p] = num[p] = 0, len[p] = l; return p ++; } void init(){ p = 0; newnode(0); newnode(-1); last = n = 0; S[n] = -1; fail[0] = 1; } int get_fail(int x){ while(S[n -len[x] - 1] != S[n]) x= fail[x]; return x; } int add(int c){ S[++n] = c; int cur = get_fail(last), f = 0; if(!nxt[cur][c]){ int now = newnode(len[cur] + 2); fail[now] = nxt[get_fail(fail[cur])][c]; nxt[cur][c] = now; num[now] = num[fail[now]] + 1; f = 1; } last = nxt[cur][c]; cnt[last]++; return f; } void _count(){ for(int i = p - 1; i >= 0; i--) cnt[fail[i]] += cnt[i];
    }
} pd;

string s;

int main()
{
    #ifdef LOCAL
    freopen("15.in", "r", stdin);
    //freopen("15.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);
    LL n, i, ans = 0;
    cin >> s;
    n = s.size();
    pd.init();
    for(i = 0; i < n; i++){
        ans += pd.add(s[i] - 'a');
        if(i != 0) cout << " " << ans;
        else cout << ans;
    }

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx