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;
}