定义
奇根 \(0\):长度为 -1 的回文串所在节点(为了便于处理)
偶根 \(1\):长度为 0 的回文串所在节点
\(len[u]\):当前节点 \(u\) 维护的回文长度
\(trans[u][c]\):转移函数,注意其中所有状态均为回文(单次转移相当于 \(u\) 节点代表字符串左右两边加上\(c\))
\(fail[u]\):失配指针,指向 \(u\) 最大匹配后缀回文的所在节点
前置理论
一个长度为 \(n\) 的字符串中,本质不同的回文子串个数也不超过 \(n\)
对于在一个串中新增一个字符的情况下,本质不同回文子串个数最多新增 1 个
证明:
考虑增量过程中新增的字符 \(str[i]\),新增的回文肯定跟它有关(也就是肯定是 \(str[j...i]\) 的形式,\(j\) 任取)
我们假设真的存在新增多个本质不同回文子串,从中挑出最长的一个串 \(s\)
可以发现其它的回文子串即使存在也是以 \(s\) 的后缀形式存在
但作为回文,后缀出现过的,那么前缀也肯定出现过,因此是属于本质相同的子串,END
因此我们可以用 \(O(n)\) 个状态转移来表示所有本质不同的回文子串
构造过程
- 偶根的失配指针指向奇根,奇根必然不会失配(单个字符也能形成回文串)
- 采用增量的方法一个一个添加字符,假设现在添加字符\(c\)
- 维护 \(str[0...i)\) 后缀的最长回文字串 \(str[j...i)\),\(j\) 任取,设所在节点为 \(u\)
- 通过不断地寻找 \(u\) 的
suffix-link
(\(fail[..fail[u]]\)),相当于缩短后缀,找到一个回文串\(X\),使得满足在原串中符合 \(cXc\) 形式的回文串,设节点为\(v\) - 如果存在,那我们不必理会,因为由状态存在得知是本质相同的(前面存在过的);否则新增 \(trans[u][c]\) 状态 \(n\) ,我们已知其长度就是 \(len[v]\) 多两个字符的长度(这个时候奇根直接 +2 就是巧妙的形成单个字符的回文串)
- 至于 \(fail[v]\),可以发现同样是同样是 \(u/w\) 的后缀加上 \(c\),直接继续在 \(w\) 的
suffix-link
上寻找符合 \(cYc\) 的状态即可,设为 \(w\),令 \(fail[v]=trans[w][c]\)
好了已经构造完了,由于找 \(fail\) 的过程会使得 \(str[j...i]\) 中的 \(j\) 不断右移,因此总体来看,其成本还是 \(O(n)\)
完成版
#include <bits/stdc++.h>
struct PT {
const std::string &str;
std::vector<std::array<int, 127>> trans;
std::vector<int> fail;
std::vector<int> len;
int odd, even;
int last;
int make(int f, int l) {
int node = trans.size();
trans.push_back({});
fail.emplace_back(f);
len.emplace_back(l);
return node;
}
PT(const std::string &str)
: str(str),
odd(make(0, -1)),
even(make(0, 0)),
last(even) {
for(int i = 0; i < str.size(); ++i) {
add(i);
}
}
void add(int index) {
int c = str[index];
int u = last;
int v = failwalk(u, index);
if(!trans[v][c]) {
int f, l;
if(len[v] == -1) {
f = even;
l = 1;
} else {
int w = failwalk(fail[v], index);
f = trans[w][c];
l = len[v] + 2;
}
int n = make(f, l);
trans[v][c] = n;
}
last = trans[v][c];
}
int failwalk(int u, int index) {
for(;;) {
int lo = index - 1 - len[u];
if(lo >= 0 && str[lo] == str[index]) break;
u = fail[u];
}
return u;
}
};
int main() {
std::string str = "aabaaa";
PT pt(str);
std::cout << *std::max_element(pt.len.begin(), pt.len.end()) << std::endl;
return 0;
}
参考
http://adilet.org/blog/palindromic-tree/