HDU7326 string magic(Easy Version)

HDU7326 string magic(Easy Version)

tag：回文自动机

题目链接

题意：

多组样例，每组输入一字符串(长度1e5以内)，输出满足下列条件的子串个数： 该串由两个完全相同的回文串拼接而成

做法：

字符串的题目一般都比较板，洛谷的P4287可以说是这道题目的原题，我们先看看原题是怎么做的

P4287 双倍回文

题意：

给出字符串，输出满足下列条件的最大子串长度：

• 字符串x由两个完全相同的回文串拼接而成
• 字符串x长度为4的倍数

做法：

• 我们使用回文自动机建立fail树，同时用vector存边准备dfs
• 我们直到树上一个节点就代表着一种回文串，节点父亲所代表的字符串则是当前节点的最长后缀回文，那么显然节点的祖先都是该点的后缀回文
• 于是我们可以在dfs的过程中计入祖先节点的长度，若存在当前节点一半长度的祖先，且当前节点长度为4的倍数，那么当前就是一个合法串。

代码

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+50;
const int mod=998244353;
const ll inf = 2e18;

namespace PAM {
    int size, tot, last;
    int cnt[N], tr[N][26], len[N], fail[N],f[N];
    char s[N];
    vector<int> g[N];
    int ans = 0;

    int node(int l) {  // 建立一个新节点，长度为 l
        size++;
        memset(tr[size], 0, sizeof(tr[size]));
        len[size] = l;
        fail[size] = cnt[size] = 0;
        return size;
    }

    void init() {  // 初始化
        size = -1; last = 0;
        s[tot = 0] = '$';
        node(0); node(-1);
        g[1].push_back(0);
        fail[0] = 1;
    }

    int getfail(int x) {  // 找后缀回文
        while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
        return x;
    }

    void add(char c) {  // 建树
        s[++tot] = c;
        int now = getfail(last);
        if(!tr[now][c]){
            int x = node(len[now] + 2);
            fail[x] = tr[getfail(fail[now])][c]; 
            g[fail[x]].push_back(x);
            tr[now][c] = x;
        }
        last = tr[now][c];
        cnt[last]++;
    }

    void dfs(int u){
        for(auto i: g[u]){
            int k = len[i];
            f[k]++;
            if(k%4==0&&f[k/2]) ans = max(ans,k);
            dfs(i);
            f[k]--;
        }
    }
}


int main(){
    PAM::init();
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        char c; cin>>c;
        PAM::add(c-'a');
    }

    PAM::dfs(1);
    cout<<PAM::ans<<le;

    return 0;
}

• 回到当前这题，判断合法串的方式可以说是几乎一模一样，但是这次我们需要统计的是出现次数，在造完PAM之后，cnt计入的是最长回文个数，回文的子串并没有统计
• 要算出所有回文串的个数可以通过dfs，或者直接从后往前做后缀和，因为父亲节点一定比儿子节点的编号小。

代码：

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
const int mod=998244353;
const ll inf = 2e18;

namespace PAM {
    int size,tot,last,ans,n;
    int cnt[N], tr[N][26], len[N], fail[N],f[N];
    char s[N];
    vector<int> g[N];

    int node(int l) {  // 建立一个新节点，长度为 l
        size++;
        memset(tr[size], 0, sizeof(tr[size]));
        len[size] = l;
        fail[size] = cnt[size] = 0;
        return size;
    }

    void init() {  // 初始化
        size = -1; last = 0;
        ans = 0;
        s[tot = 0] = '$';
        node(0); node(-1);
        g[1].push_back(0);
        fail[0] = 1;
    }

    int getfail(int x) {  // 找后缀回文
        while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
        return x;
    }

    void add(char c) {  // 建树
        s[++tot] = c;
        int now = getfail(last);
        if(!tr[now][c]){
            int x = node(len[now] + 2);
            fail[x] = tr[getfail(fail[now])][c]; 
            g[fail[x]].push_back(x);
            tr[now][c] = x;
        }
        last = tr[now][c];
        cnt[last]++;
    }

    void dfs(int u){
        for(auto i: g[u]){
            int k = len[i];
            f[k]++;
            if(k>=2&&k%2==0&&f[k/2]) ans += cnt[i];
            dfs(i);
            f[k]--;
        }
    }

    void cl(){
        for(int i=0;i<=size;i++) g[i].clear();
    }
}

void solve(){
    string s; cin>>s;
    PAM::init();
    for(auto i: s) PAM::add(i-'a');
    for(int i=PAM::size;i>=2;i--) PAM::cnt[PAM::fail[i]] += PAM::cnt[i]; 
    PAM::dfs(1);
    cout<<PAM::ans<<le;
    PAM::cl();
}

int main(){
    int t; cin>>t;
    while(t--){
        solve();
    }

    return 0;
}