題目鏈接

題意

一個長度為3e5的字符串，求長度為$i$的字符串滿足字符是回文串而且字符串的前一半也是回文串的個數

思路

回文數求出所有的回文字符串，然后用Manacher或者Hash判斷是否符合條件

#include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 #define endl '\n' const int maxn = 3e5 + 5; const int inf = 0x3f3f3f3f; const int mod = 19930726; using namespace std;struct Palindrome_Tree{int nex[maxn][26];int fail[maxn], cnt[maxn], num[maxn]; // num 記錄每個節點右端點的表示回文串的個數int len[maxn], S[maxn]; // cnt 記錄每個節點表示的回文串出現的次數int last, n, p;int newnode(int l) { // 新建節點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) { // 添加節點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 >= 0; --i) cnt[fail[i]] += cnt[i];} }Tree; int RL[maxn << 1]; void Manacher(string s) {string t;for (int i = 0; i < (int)s.size(); ++i) {t += s[i];t += '#';}s = "#" + t;int MaxRight = 0, pos = 0;for (int i = 0; i < (int)s.size(); ++i) {if (i < MaxRight) RL[i] = min(RL[2 * pos - i], MaxRight - i + 1); // 好多這里寫的是 MaxRight - i，個人感覺根據算法思想應該+1計算長度。else RL[i] = 1;int l = i - RL[i];int r = i + RL[i];while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {RL[i] += 1;l = i - RL[i];r = i + RL[i];}if (RL[i] + i - 1 > MaxRight) {MaxRight = RL[i] + i - 1;pos = i;}} } int ans[maxn], pos[maxn]; int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);string s;while (cin >> s) {int len = s.size();Tree.init();for (int i = 0; i <= len * 2; ++i) RL[i] = 0;for (int i = 1; i <= len; ++i) ans[i] = 0;Manacher(s);for (int i = 0; i < len; ++i) {Tree.add(s[i]);pos[Tree.last] = i; }Tree.count();for (int i = 2; i < Tree.p; ++i) {int t = Tree.len[i] / 2;int idx = (pos[i] - t - (Tree.len[i] - t) / 2) * 2 + 1;if ((Tree.len[i] - t) % 2 == 0) idx += 1; if (RL[idx] - 1 >= Tree.len[i] - t) {ans[Tree.len[i]] += Tree.cnt[i];}}for (int i = 1; i <= len; ++i) {if (i > 1) cout << " ";cout << ans[i];}cout << endl;}return 0; } #include <bits/stdc++.h> #define LL long long #define P pair<int, int> #define lowbit(x) (x & -x) #define mem(a, b) memset(a, b, sizeof(a)) #define mid ((l + r) >> 1) #define lc rt<<1 #define rc rt<<1|1 #define endl '\n' const int maxn = 3e5 + 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 記錄每個節點右端點的表示回文串的個數int len[maxn], S[maxn]; // cnt 記錄每個節點表示的回文串出現的次數int last, n, p;int newnode(int l) { // 新建節點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) { // 添加節點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 >= 0; --i) cnt[fail[i]] += cnt[i];} }Tree; int ans[maxn], pos[maxn]; struct Hash{long long p[maxn], hash[maxn], seed = 402653189;long long getHash(int l, int r) {long long ans = (hash[r] - hash[l-1] * p[r-l+1]) % mod;return (ans + mod) % mod;}void init(string s) {int n = s.size();p[0] = 1;for (int i = 1; i <= n; ++i) p[i] = p[i - 1] * seed % mod;for (int i = 1; i <= n; ++i) {hash[i] = (hash[i - 1] * seed % mod + (s[i-1] - 'a' + 1)) % mod;}} }hash1, hash2; int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);string s;while (cin >> s) {int len = s.size();for (int i = 1; i <= len; ++i) ans[i] = 0;Tree.init();for (int i = 0; i < len; ++i) {Tree.add(s[i]);pos[Tree.last] = i; }Tree.count();hash1.init(s);reverse(s.begin(), s.end());hash2.init(s);for (int i = 2; i < Tree.p; ++i) {int t = Tree.len[i] / 2;int l = pos[i] - Tree.len[i] + 2;int r = pos[i] - t + 1;if (hash1.getHash(l, r) == hash2.getHash(len+1-r, len+1-l)) {ans[Tree.len[i]] += Tree.cnt[i];}}for (int i = 1; i <= len; ++i) {if (i > 1) cout << " ";cout << ans[i];}cout << endl;}return 0; }

總結

以上是生活随笔為你收集整理的HDU - 6599 I Love Palindrome String (回文树+Manacher、回文树+hash)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。