回文自动机PAM
title: 回文自动机PAM
categories:
- ICPC
tags:
- null
abbrlink: e5a7c7ec
date: 2024-08-04 00:00:00
回文自动机PAM
每个状态仅代表唯一的本质不同的回文子串字符串 。s 的本质不同回文子串的数量至多只有 |s|个，则 PAM 的状态数个数是 O(n)级别的
算法原理就是增量法构建 PAM，利用前面的回文后缀，fail指针配合转移边进行维护。
算法核心流程：
- 1.加入新节点的时候找到以这个点的结尾的最长回文后缀，需要跑last,last—>fail,last—>fail->fail,直到有转移边或者有奇根。目的是找到新建节点的父亲。
- 为新建节点找到不平凡的最长回文回文后缀(也就是不包含自身)。这一步骤爬上一步(找到的父亲)(的fail链)（不包含父亲）
struct PAM {
static constexpr int asz = 28;
struct Node {
int len;
int fail;
int dep; // 以这个节点结尾的回文子串的数量(回文fail树的深度)
int cnt = 0; // 同样的回文结构出现次数
array<int, asz> next;
// int mask = 0;用了多少种字母
Node() : len{}, fail{}, dep{}, next{} {}
};
vector<Node> t;
vector<int> idpos; // idpos表示字符串字符位置到后缀自动机节点编号
int last;
string s;
PAM() {
init();
}
void init() {
t.assign(2, Node());
t[0].len = -1; // 0：奇根
last = 1; // 1：偶根
s.clear();
idpos.assign(1, 0);
}
int newNode() {
t.emplace_back(); // Node()
return t.size() - 1;
}
bool add(char c, char offset = 'a') {
int pos = s.size();
s += c;
int ch = c - offset;
int cur = last, curlen = 0;
while (true) {
curlen = t[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
break;
cur = t[cur].fail;
} // 找到在哪个节点后面建新点
if (t[cur].next[ch]) {
last = t[cur].next[ch];
idpos.push_back(last);
t[last].cnt += 1;
return false;
}
int num = newNode();
last = num;
idpos.push_back(last);
t[num].len = t[cur].len + 2;
// 在这里加入题目需要维护的值
// t[num].mask = t[cur].mask;
// t[num].mask |= 1 << ch;
t[cur].next[ch] = num;
if (t[num].len == 1) { // 如果为单字符，指向偶根
t[num].fail = 1;
t[num].dep = 1;
t[num].cnt = 1;
return true;
}
while (true) { // 为新节点找fail，从父亲的fail开始找
cur = t[cur].fail;
curlen = t[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
t[num].fail = t[cur].next[ch];
break;
}
}
t[num].cnt = 1;
t[num].dep = 1 + t[t[num].fail].dep;
return true;
}
int tot = 0;
void work(string tt) {
for (auto x : tt) add(x);
tot = t.size() - 1;
for (int i = tot; i >= 2; i--) {
int fa = t[i].fail;
t[fa].cnt += t[i].cnt;
}
}
int fail(int p) {
return t[p].fail;
}
int len(int p) {
return t[p].len;
}
int size() {
return t.size();
}
int cnt(int p) {
return t[p].cnt;
}
};
【模板】回文自动机（PAM）https://www.luogu.com.cn/problem/P5496P5496 输出以第 i 个字符结尾的回文子串个数,强制在线
Sol:建出回文自动机，考虑维护深度就是以当前节点结尾的回文后缀个数，只在新节点的时候需要维护。dp考虑即可dp[u]=dp[fail[u]]+1;
PAM pam;
void solve() {
string s;
cin >> s;
int last = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (i == 0)
pam.add(s[i]);
else {
char c = (s[i] - 97 + last) % 26 + 97;
pam.add(c);
}
last = pam.t[pam.idpos[i + 1]].dep;
cout << last <<" ";
}
}
[APIO2014] 回文串https://www.luogu.com.cn/problem/P3649
我们定义 $s$ 的一个子串的价值为这个子串在 $s$ 中出现的次数乘以这个子串的长度。求所有回文子串中的最大价值。
Sol：维护cnt表示出现次数，每次作为结尾节点的时候+1.最后出现次数就是fail树内的tot全加起来，为了减少常数不去建fail树然后dfs。考虑直接按编号逆序拓扑更新求和。
PAM pam;
void solve() {
string s;
cin >> s;
pam.work(s);
ll ans = 0;
int tot = pam.size() - 1;
for (int i = 2; i <= tot; i++) ans = max(ans, (ll)pam.len(i) * pam.t[i].cnt);
cout << ans << endl;
}
P4287 [SHOI2011] 双倍回文
记字符串 $w$ 的倒置为 $w^{\mathsf R}$。例如$\tt (abcd)^{\mathsf R}=dcba$，$\tt (abba)^{\mathsf R}=abba$。
如果 $x$ 能够写成 $ww^{\mathsf R} ww^{\mathsf R}$ 形式，则称它是一个“双倍回文”。换句话说，若要 $x$ 是双倍回文，它的长度必须是 $4$ 的倍数，而且 $x$，$x$ 的前半部分，$x$ 的后半部分都要是回文。例如 $\tt abbaabba$ 是一个双倍回文，而 $\tt abaaba$ 不是，因为它的长度不是 $4$ 的倍数。
对于给定的字符串，计算它的最长双倍回文子串的长度。
Sol:所有解法都基于一个事实就是：双倍回文存在一个长度为len/2的回文后缀。-
或者说显然的观察是len/2是双倍回文的border，又由于回文串的border一定是回文后缀，所以结论正确。
解法1：从border角度考虑：我们记录每次传进来的字符的位置，然后选判长度整除4，再用提前处理好的字符串哈希判$前一半=后一半$
int ans = 0; Hash hs; int res = 0; struct PAM { static constexpr int asz = 28; struct Node { int len; int fail; int cnt; // 以这个节点结尾的回文子串的数量 int tot = 0; // 同样的回文结构出现次数 array<int, asz> next; Node() : len{}, fail{}, cnt{}, next{} {} }; vector<Node> t; int last; string s; PAM() { init(); } void init() { t.assign(2, Node()); t[0].len = -1; // 0：奇根 last = 1; // 1：偶根 s.clear(); } int newNode() { t.emplace_back(); // Node() return t.size() - 1; } bool add(int tmppos, char c, char offset = 'a') { int pos = s.size(); s += c; int ch = c - offset; int cur = last, curlen = 0; while (true) { curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break; cur = t[cur].fail; } // 找到在哪个节点后面建新点 if (t[cur].next[ch]) { last = t[cur].next[ch]; t[last].tot += 1; return false; } int num = newNode(); last = num; t[num].len = t[cur].len + 2; t[cur].next[ch] = num; if (t[num].len == 1) { // 如果为单字符，指向偶根 t[num].fail = 1; t[num].cnt = 1; t[num].tot = 1; return true; } while (true) { // 为新节点找fail，从父亲的fail开始找 cur = t[cur].fail; curlen = t[cur].len; if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) { t[num].fail = t[cur].next[ch]; break; } } t[num].tot = 1; t[num].cnt = 1 + t[t[num].fail].cnt; if (t[num].len % 4 == 0) { int tmplen = t[num].len / 2; int l1 = tmppos - t[num].len + 1; int l2 = l1 + tmplen; if (hs.getpre(l1, l1 + tmplen - 1) == hs.getpre(l2, l2 + tmplen - 1)) { res = max(res, t[num].len); } } return true; } }; PAM pam; void solve() { cin >> n; string s; cin >> s; hs.init(s); for (int i = 0; i < n; i++) pam.add(i + 1, s[i]); cout << res << endl; }解法2：从PAM树角度考虑：我们需要爬fail链去查询是否存在一个祖先节点的长度是当前节点的一半。我们建出fail树，dfs一遍同时维护当前哪些节点是祖先，存的是他们的长度。
细节：从偶根（1）开始dfs。
PAM pam; void solve() { cin >> n; string s; cin >> s; for (auto x : s) pam.add(x); auto t = pam.t; int tot = t.size() - 1; vector<vector<int>> e(tot + 3); for (int i = 2; i <= tot; i++) e[t[i].fail].push_back(i); vector<bool> st(n + 1); int ans = 0; auto dfs = [&](auto self, int u) -> void { int lenu = t[u].len; if (lenu % 4 == 0 && st[lenu / 2]) { ans = max(ans, lenu); } st[lenu] = 1; for (auto v : e[u]) { self(self, v); } st[lenu] = 0; }; dfs(dfs, 1); cout << ans << endl; }提供一种接近本质的做法：直接增加一个trans指针，维护fail的时候也维护它。trans 指针的含义是小于等于当前节点长度一半的最长回文后缀，求法和 fail指针的求法类似。来源：https://www.luogu.com.cn/article/gx0icv96
由于回文自动机可能会被卡空间，开成全局变量了
https://qoj.ac/contest/1440/problem/7876给出字符串，定义价值为$出现次数\times 出现次数\times长度$，求所有回文区间串的价值总和。区间串的定义如下：
- $i\le j \quad s[i..j]$
- $i>j \quad s[i..n] + s[1..j]$
Sol:首先考虑只有$len \le n$的回文子串才能贡献。再考虑我们需要处理循环位移，不难想到倍长原串，所以会出现重复计算次数的情况，怎么处理？考虑重复的情况一定会在结尾0-n的时候遇到，所以我们对于$0-n$的时候对原串和倍长串都统计次数，两者之差就减去了单独这个串的影响。$n-2n-1$这段不会出现重复，但需要注意控制长度在$1-n$内就可以了。
PAM pam1;
PAM pam2;
void solve() {
ll ans = 0;
string s;
cin >> n >> s;
pam1.work(s);
pam2.work(s + s);
auto &t1 = pam1.t, t2 = pam2.t;
vector<bool> mp(pam2.tot + 5, 0);
for (int i = 0; i < n; i++) {
int u1 = pam1.idpos[i], u2 = pam2.idpos[i];
if (mp[u2])
continue;
mp[u2] = true;
int cnt = t2[u2].cnt - t1[u1].cnt;
ans += (((ll)cnt * cnt % mod) * (ll)t2[u2].len) ;
ans %= mod;
}
for (int i = n; i < 2 * n; i++) {
int u = pam2.idpos[i];
if (mp[u])
continue;
mp[u] = true;
if (t2[u].len > n)
continue;
int cnt = t2[u].cnt;
ans += (((ll)cnt * cnt % mod) * (ll)t2[u].len);
ans %= mod;
}
cout << ans << endl;
}
给出一个字符串S，定义一个字符串的价值为：出现字母的种类数。
求S 所有回文子串的价值之和。
Sol：本题除了求每个本质不同子串的出现次数外，还需要求每个本质不同子
串出现的字母种类数。
可以在PAM 的每个节点额外维护一个mask，表示这个点代表的回文串
用到了哪些字母，在新建节点的时候顺便维护即可
struct Node {
int len;
int fail;
int dep; // 以这个节点结尾的回文子串的数量(回文fail树的深度)
int cnt = 0; // 同样的回文结构出现次数
array<int, asz> next;
int mask = 0;
Node() : len{}, fail{}, dep{}, next{} {}
};
bool add(char c, char offset = 'a') {
int pos = s.size();
s += c;
int ch = c - offset;
int cur = last, curlen = 0;
while (true) {
curlen = t[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
break;
cur = t[cur].fail;
} // 找到在哪个节点后面建新点
if (t[cur].next[ch]) {
last = t[cur].next[ch];
idpos.push_back(last);
t[last].cnt += 1;
return false;
}
int num = newNode();
last = num;
idpos.push_back(last);
t[num].len = t[cur].len + 2;
// 在这里加入题目需要维护的值
t[num].mask = t[cur].mask;
t[num].mask |= 1 << ch;
t[cur].next[ch] = num;
if (t[num].len == 1) { // 如果为单字符，指向偶根
t[num].fail = 1;
t[num].dep = 1;
t[num].cnt = 1;
return true;
}
while (true) { // 为新节点找fail，从父亲的fail开始找
cur = t[cur].fail;
curlen = t[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
t[num].fail = t[cur].next[ch];
break;
}
}
t[num].cnt = 1;
t[num].dep = 1 + t[t[num].fail].dep;
return true;
}
void solve() {
ll ans = 0;
string s;
cin >> s;
PAM pam;
pam.work(s);
int tot = pam.size() - 1;
for (int i = 2; i <= tot; i++) ans += pam.cnt(i) * __builtin_popcount(pam.t[i].mask);
cout << ans << endl;
}
给出一个字符串S，|S| ≤ 1000, 000。求前K 大的奇回文子串奇数长度乘积。
K ≤ 1000, 000, 000
Sol:回文自动机建出来。拓扑序求出出现次数，存到桶里，倒序模拟，快速幂富足计算。值得注意的是题目只要奇数长度的回文串，注意读题
void solve() {
ll n, k;cin >> n >> k;
string s;cin >> s;
PAM pam;pam.work(s);
vector<int> a(n + 1);
int tot = pam.size() - 1;
ll ans = 1;
for (int i = 2; i <= tot; i++) {
a[pam.len(i)] += pam.cnt(i);
}
// 注意读题:不要偶数回文
for (int i = n; i >= 1; i--) {
if (i % 2 == 0)continue;
if (k - a[i] >= 0) {
ans = (ans * qmi(i, a[i])) % mod;
k -= a[i];
} else {
ans = (ans * qmi(i, k)) % mod;
k = 0;
break;
}
}
if (k)
cout << -1;
else
cout << ans << endl;
}
给出一个字符串S，求最长的双回文子串。
回文双子串T 定义为：可以从一个位置切开，使得前缀和后缀都是回文
串。
|S| ≤ 100, 000.
Sol:可以枚举拼接点pos，然后分别最大化以pos为左端点pos+1为右端点的回文串长度。问题转化为求某个点最长回文前缀后缀，开两个回文自动机，对正串反串跑一遍即可。枚举拼接点，更新答案$pam1.len(idpos(i))+pam2.len(idpos(n+1-i))$.注意反串的坐标映射
void solve() {
PAM pam;
string s;
cin >> s;
string rs = s;
reverse(alls(rs));
PAM par;
pam.work(s);
par.work(rs);
int n = s.size();
int ans = 0;
for (int i = 1; i <= n - 1; i++) {
int pre = par.idpos[n + 1 - (i + 1)], suf = pam.idpos[i];
ans = max(ans, pam.len(suf) + par.len(pre));
}
cout << ans << endl;
}
给出一个01 串S，求最长的反对称子串。
反对称串T 定义为：将R(T) 逐位取反之后等于原串T，则T 是一个反
对称串，例如010101。
|S| ≤ 500, 000
Sol:考虑在新的相等运算意义下进行Manacher 即可。注意到奇数长度一定非法，因为中间字符没办法相等。统计答案的时候只统计偶数长度的，再考虑初始化的时候，单个字符构成的半径显然是0，因为它本身不能构成反对称串。
bool defeq(char c, char d) {
if (c == '#' && d == '#')
return true;
int cc = c - '0', dd = d - '0';
if (cc == 0 && dd == 1)
return true;
if (cc == 1 && dd == 0)
return true;
return false;
}
struct PAS {
string s = "#";
int len = 1;
vector<int> p;
// vector<pair<int, int>> all;
PAS(string t) {
for (auto c : t) {
s += c;
s += '#';
len += 2;
}
s = " " + s;
p.resize(len + 1);
deb(s);
getp(s);
}
vector<int> getp(string t) {
int mid = 0, r = 0;
for (int i = 1; i <= len; i++) {
if (i > r) {
p[i] = 0;
} else
p[i] = min(p[2 * mid - i], r - i + 1);
while (i - p[i] > 0 && i + p[i] <= len && defeq(t[i - p[i]], t[i + p[i]])) {
p[i] += 1;
// int ql, qr;
// if ((i - p[i] + 1) % 2 == 0)
// ql = (i - p[i] + 1) / 2;
// else
// ql = (i - p[i] + 2) / 2;
// if ((i + p[i] - 1) % 2 == 0)
// qr = (i + p[i] - 1) / 2;
// else
// qr = (i + p[i] - 2) / 2;
// all.emplace_back(ql, qr);
}
// deb(i,s[i],p[i]);
if (i + p[i] - 1 > r)
mid = i, r = i + p[i] - 1;
}
return p;
}
int getmax() {
int ans = 0;
for (int i = 1; i <= len; i++) {
ans = max(ans, p[i]);
}
return (ans - 1);
}
};
void solve() {
ll ans = 0;
int n;
string s;
cin >> n >> s;
PAS pas(s);
deb(pas.p);
for (int i = 1; i <= pas.len; i++) {
if (i % 2)
ans += pas.p[i] / 2;
}
cout << ans << endl;
}
https://www.luogu.com.cn/problem/P4656
[CEOI2017] Palindromic Partitions
题目描述
给出一个只包含小写字母字符串，要求你将它划分成尽可能多的小块，使得这些小块构成回文串。
例如：对于字符串 abcab，将他分成 ab c ab 或者 abcab 就是构成回文串的划分方法，abc ab 则不是。abcab把ab看做一个整体元素，ab=x.则xcx是回文串。考虑最坏情况整个串看作一个整体，再贪心考虑每次从当前指针指向前后缀找最短非零的border，可以用字符串哈希实现。
void solve() {
string s;
cin >> s;
Hash hs1(s);
int n = s.size();
int ql = 1, qr = n;
int len = 0, cnt = 0;
deb(s);
deb(hs1.getpre(1, 2));
while (ql + len < qr - len) {
deb(ql, qr, len);
if (hs1.getpre(ql, ql + len) == hs1.getpre(qr - len, qr)) {
ql += len + 1;
qr -= len + 1;
len = 0;
cnt += 2;
} else {
len++;
}
}
if(len||ql==qr)cnt+=1;
cout << cnt << endl;
}
https://ac.nowcoder.com/acm/problem/13230
【每日一题】3月26日题目精讲 区间dp、最长回文子序列_ACM竞赛_ACM/CSP/ICPC/CCPC/比赛经验/题解/资讯_牛客竞赛OJ_牛客网 (nowcoder.com)