題目鏈接

題意

一個字符串，求有多少對$(S，T)$，滿足$S、T$是回文串，$S是T的子串$

思路

題解還沒看懂…
看大佬代碼，好多在回文樹上$dfs$
$sz[i]$表示nex往下能走多少，節(jié)點$i$左右能加多少字符串
$c[i]$表示fail向上能走多少，節(jié)點$i$有多少后綴相同的回文串
$sz[i]\times c[i]$就是節(jié)點$i$對答案的貢獻

#include <bits/stdc++.h> #define endl '\n' const int maxn = 1e5 + 5; const int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; using namespace std; struct Palindrome_Tree{int nex[maxn][26];int fail[maxn], cnt[maxn], num[maxn]; // num 記錄每個節(jié)點右端點的表示回文串的個數(shù)int len[maxn], S[maxn]; // cnt 記錄每個節(jié)點表示的回文串出現(xiàn)的次數(shù)int last, n, p;int sz[maxn], c[maxn], vis[maxn];int newnode(int l) { // 新建節(jié)點for (int i = 0; i < 26; ++i) nex[p][i] = 0;cnt[p] = num[p] = 0;len[p] = l;return p++;}void init() { // 初始化p = 0;newnode(0), newnode(-1); // 新建奇根和偶根last = n = 0;S[n] = -1;fail[0] = 1; // 偶根指向}int get_fail(int x) { // 求failwhile (S[n - len[x] - 1] != S[n]) x = fail[x];return x;}void add(int c) { // 添加節(jié)點c -= 'a';S[++n] = c;int cur = get_fail(last);if (!nex[cur][c]) {int now = newnode(len[cur] + 2);fail[now] = nex[get_fail(fail[cur])][c];nex[cur][c] = now;num[now] = num[fail[now]] + 1;}last = nex[cur][c];cnt[last]++;}void count() { // 求cntfor (int i = p - 1; i >= 2; --i) cnt[fail[i]] += cnt[i];}int dfs(int u) {sz[u] = 1;c[u] = 0;for (int t = u; !vis[t] && t > 1; t = fail[t]) {vis[t] = u;c[u]++;}for (int i = 0; i < 26; ++i) {if (nex[u][i] == 0) continue;sz[u] += dfs(nex[u][i]); }for (int t = u; vis[t] == u && t > 1; t = fail[t]) {vis[t] = 0;}return sz[u];}long long solve() {dfs(0), dfs(1);long long ans = 0;for (int i = 2; i < p; ++i) {ans += 1ll * sz[i] * c[i];}return ans - p + 2;} }Tree; char s[maxn]; int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T, Case = 1;scanf("%d", &T);while (T--) {scanf("%s", s);Tree.init();for (int i = 0; s[i]; ++i) {Tree.add(s[i]);}printf("Case #%d: %lld\n", Case++, Tree.solve());}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2019牛客暑期多校训练营（第六场）C - Palindrome Mouse (回文树dfs)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。