回文树总结二 2019徐州网络赛 Colorful String 和 湖南大学第十五届程序设计竞赛 H.Longest Common Palindrome Substring
Colorful String
问你 每个回文串 有多少不同字符 累和 输出
回文树 统计回文串 DFS遍历 所有回文串 统计
https://nanti.jisuanke.com/t/41389
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300005;// n(空间复杂度o(n*ALP)),实际开n即可
const int ALP = 26;
struct PAM{ // 每个节点代表一个回文串
int nxt[maxn][ALP]; // nxt指针,参照Trie树
int fail[maxn]; // fail失配后缀链接
int cnt[maxn]; // 此回文串出现个数
int num[maxn];
int len[maxn]; // 回文串长度
int s[maxn]; // 存放添加的字符
int last; //指向上一个字符所在的节点，方便下一次add
int n; // 已添加字符个数
int p; // 节点个数
int newnode(int w){ // 初始化节点，w=长度
for(int i=0;i<ALP;i++)
nxt[p][i] = 0;
cnt[p] = 0;
num[p] = 0;
len[p] = w;
return p++;
}
void init(){
p = 0;
newnode(0);
newnode(-1);
last = 0;
n = 0;
s[n] = -1; // 开头放一个字符集中没有的字符，减少特判
fail[0] = 1;
}
int get_fail(int x){ // 和KMP一样，失配后找一个尽量最长的
while(s[n-len[x]-1] != s[n]) x = fail[x];
return x;
}
void add(int c){
c -= 'a';
s[++n] = c;
int cur = get_fail(last);
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;
}
last = nxt[cur][c];
cnt[last]++;
}
void count(){
// 最后统计一遍每个节点出现个数
// 父亲累加儿子的cnt,类似SAM中parent树
// 满足parent拓扑关系
for(int i=p-1;i>=0;i--)
cnt[fail[i]] += cnt[i];
}
long long dfs(int now, int vis) {
int num = 0;
long long res = 0;
for(int i = 0; i < ALP; i ++) if(vis >> i & 1) num ++;
if(now >= 2) res += num * cnt[now];
for(int i = 0; i < ALP; i ++) {
if(nxt[now][i]) res += dfs(nxt[now][i], vis|(1 << i));
}
return res;
}
long long getans() {
long long res = 0;
res = dfs(0, 0);
res += dfs(1, 0);
return res;
}
}pam;
char s[maxn];
int main() {
scanf("%s", s);
int len = strlen(s);
pam.init();
for(int i = 0; i < len; i ++) pam.add(s[i]);
pam.count();
printf("%lld\n", pam.getans());
return 0;
}
湖南大学第十五届程序设计竞赛 H.Longest Common Palindrome Substring
https://ac.nowcoder.com/acm/contest/908/H
最长公共回文串 直接 dfs 共有的回文串就好
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300005;// n(空间复杂度o(n*ALP)),实际开n即可
const int ALP = 26;
struct PAM{ // 每个节点代表一个回文串
int nxt[maxn][ALP]; // nxt指针,参照Trie树
int fail[maxn]; // fail失配后缀链接
int cnt[maxn]; // 此回文串出现个数
int num[maxn];
int len[maxn]; // 回文串长度
int s[maxn]; // 存放添加的字符
int last; //指向上一个字符所在的节点，方便下一次add
int n; // 已添加字符个数
int p; // 节点个数
int newnode(int w){ // 初始化节点，w=长度
for(int i=0;i<ALP;i++)
nxt[p][i] = 0;
cnt[p] = 0;
num[p] = 0;
len[p] = w;
return p++;
}
void init(){
p = 0;
newnode(0);
newnode(-1);
last = 0;
n = 0;
s[n] = -1; // 开头放一个字符集中没有的字符，减少特判
fail[0] = 1;
}
int get_fail(int x){ // 和KMP一样，失配后找一个尽量最长的
while(s[n-len[x]-1] != s[n]) x = fail[x];
return x;
}
void add(int c){
c -= 'a';
s[++n] = c;
int cur = get_fail(last);
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;
}
last = nxt[cur][c];
cnt[last]++;
}
void count(){
// 最后统计一遍每个节点出现个数
// 父亲累加儿子的cnt,类似SAM中parent树
// 满足parent拓扑关系
for(int i=p-1;i>=0;i--)
cnt[fail[i]] += cnt[i];
}
}p1, p2;
char s1[maxn], s2[maxn];
int dfs(int n1, int n2) {
int res = max(p1.len[n1], 1);
for(int i = 0; i < 26; i ++) {
if(p1.nxt[n1][i] && p2.nxt[n2][i]) {
res = max(res, p1.len[n1]);
res = max(res, dfs(p1.nxt[n1][i], p2.nxt[n2][i]));
}
}
return res;
}
int main() {
while(scanf("%s", s1) != EOF) {
scanf("%s", s2);
p1.init(), p2.init();
int len1 = strlen(s1), len2 = strlen(s2);
for(int i = 0; i < len1; i ++) p1.add(s1[i]);
for(int i = 0; i < len2; i ++) p2.add(s2[i]);
printf("%d\n", max(dfs(0, 0), dfs(1, 1)));
}
return 0;
}
