**Gợi ý**: Với mỗi vị trí $i$ trong xâu, ta sẽ tìm xem số lượng xâu đối xứng có độ dài chẵn và số lượng xâu đối xứng có độ dài lẻ với $i$ là trung tâm.
Chúng ta có thể sử dụng thuật toán Manacher để có thể thực hiện điều đó. Bạn cũng có thể tham khảo thuật toán này [Tại đây](https://wiki.vnoi.info/vi/algo/string/manacher)
**Code**:
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define el '\n'
#define FOR(i, a, b) for (int i=(a), _b = (b) ; i<=_b ; i++)
#define FORD(i, a, b) for (int i=(a), _b = (b) ; i>=_b ; i--)
#define REP(i, n) for (int i=0, _n=(n) ; i<_n ; i++)
#define fi first
#define se second
template <class T> bool ckmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <class T> bool ckmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <class T> void read(T &a) { for (auto &x : a) cin >> x; }
template <class T> void print(T &a) { for (auto x : a) cout << x << " "; cout << el; }
template <class T> void is_ok(T a) { cout << (a ? "YES" : "NO") << el; }
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using Heap = priority_queue <T, vector<T>, greater<T>>;
const int N = 1e5 + 1;
int n, d_even[N], d_odd[N];
string s;
void cal_odd() {
int L = 1, R = 0;
FOR(i, 1, n) {
if (i > R) d_odd[i] = 0;
else d_odd[i] = min(R - i, d_odd[L + (R - i)]);
while (i + d_odd[i] + 1 <= n && i - d_odd[i] - 1 >= 1 && s[i + d_odd[i] + 1] == s[i - d_odd[i] - 1]) {
d_odd[i]++;
}
if(i + d_odd[i] > R) {
R = i + d_odd[i];
L = i - d_odd[i];
}
}
}
void cal_even() {
int L = 1, R = 0;
FOR(i, 1, n - 1) {
int j = i + 1;
if (j > R) d_even[i] = 0;
else d_even[i] = min(R - j + 1, d_even[L + (R - j)]);
while (j + d_even[i] <= n && i - d_even[i] >= 1 && s[j + d_even[i]] == s[i - d_even[i]]) {
d_even[i]++;
}
if (j + d_even[i] - 1 > R) {
R = j + d_even[i] - 1;
L = i - d_even[i] + 1;
}
}
}
void process() {
cin >> s;
n = s.size();
s = ' ' + s;
cal_even();
cal_odd();
int ans = 0;
FOR(i, 1, n) {
ans += d_odd[i] + 1;
}
FOR(i, 1, n - 1) {
ans += d_even[i];
}
cout << ans << el;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int nums_process = 1; //cin >> nums_process;
for (int i=1 ; i<=nums_process ; i++) process();
}
```
Một cách giải khác của bài này là sử dụng cấu trúc dữ liệu **Cây Palindrome** (hay còn gọi là Eertree).
Cấu trúc dữ liệu này có thao tác xây dựng là O(n) và truy vấn đếm số lượng xâu con Palindrome là O(n).
Các bạn có thể tham khảo chi tiết thêm về thuật toán qua những tài liệu sau:
- VNOI Wiki: [Palindrome tree](https://wiki.vnoi.info/translate/codeforces/palindrome-tree)
- GeeksforGeeks: [Palindromic Tree | Introduction & Implementation](https://www.geeksforgeeks.org/dsa/palindromic-tree-introduction-implementation)
- Codeforces adamant's blog - [Palindromic tree: behind the scenes](https://codeforces.com/blog/entry/13959)
- Codeforces Sangeet.cpp's blog - [Eertree (Palindromic Tree) — Comprehensive Resource Guide](https://codeforces.com/blog/entry/147567)
**Cài đặt mẫu:**
```
#include <bits/stdc++.h>
using namespace std;
#define mset(x,val) memset(x,val,sizeof(x))
#define allof(x) x.begin(), x.end()
#define fi first
#define se second
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using vb = vector<bool>;
using vbb = vector<vector<bool>>;
using mii = map<int,int>;
using umii = unordered_map<int,int>;
using pii = pair<int,int>;
using pll = pair<long long,long long>;
using pli = pair<long long, int>;
using pil = pair<int, long long>;
#define __builtin_popcount __builtin_popcountll
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))
#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
int a, b, m, n, k, q;
struct Eertree
{
struct Node
{
int len;
int link;
int next[26];
ll cnt;
ll s_cnt;
int first_pos;
Node (int _n)
{
len = _n;
link = 0;
cnt = 0;
s_cnt = 0;
mset(next, 0);
}
};
int n;
vector <Node> tree;
string s;
int last;
Eertree(int _n)
{
n = _n;
tree.reserve(n+3);
tree.push_back(Node(-1));
tree.push_back(Node(0));
tree[0].link = 0;
tree[1].link = 0;
last = 1;
s="";
}
int get_link(int v, int pos)
{
while (1)
{
int curlen = tree[v].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
v = tree[v].link;
}
return v;
}
void add_char(char c)
{
int pos = s.size();
s+=c;
int cur = get_link(last, pos);
int cidx = c-'a';
if (tree[cur].next[cidx])
{
last = tree[cur].next[cidx];
tree[last].cnt++;
tree[last].s_cnt++;
return;
}
int new_node = tree.size();
tree.push_back(Node(tree[cur].len + 2));
tree[new_node].first_pos = pos;
tree[cur].next[cidx] = new_node;
if (tree[new_node].len == 1) tree[new_node].link = 1;
else
{
int num = get_link(tree[cur].link, pos);
tree[new_node].link = tree[num].next[cidx];
}
tree[new_node].cnt = 1;
tree[new_node].s_cnt = 1;
last = new_node;
}
void build(string str)
{
for (char c : str) add_char(c);
}
void propagate()
{
for (int i=tree.size()-1; i>=2; --i)
{
tree[tree[i].link].s_cnt += tree[i].s_cnt;
}
}
int distinct_palin_cnt()
{
return tree.size() - 2;
}
ll palin_cnt()
{
ll res=0;
for (int i=2; i<tree.size(); ++i) res+=tree[i].s_cnt;
return res;
}
};
string s;
void Input()
{
cin>>s;
Eertree Eet = Eertree(s.size());
Eet.build(s);
Eet.propagate();
cout<<Eet.palin_cnt();
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Input();
return 0;
}
```
Thanhmay2005
Created at
2 likes
NotAndy
Created at
1 likes