这道题显然可以用PAM做出来。
PAM可以算出以字符串的第ii个字符为结尾的回文子串的个数。我们将其存到一个数组l[n]，再求一个前缀和就可以把字符串的前i个字符的前缀有多少个回文子串求出来。
然后，我们将PAM清空，倒着做一遍，就可以求出以第i个字符为左端点的回文子串个数r[i]。与它不相交的回文子串且在它前面的子串有l[i - 1]个，相乘再累加就是答案。
此题在落谷的评级是绿，那是因为此题数据范围只有2000，不用PAM也可以做。但此题可以当做PAM入门的练手题。
#include <iostream> #include <cstdio> #include <cstring> #define ll long long using namespace std; const int N = 200000; struct Plalindromic_Tree{ int go[26], len, fail; ll fail_len; }pt[N]; int lst, tot; char s[N], ss[N]; void build() { lst = tot = 0; ss[0] = -1; pt[++tot].len = -1; pt[0].fail = pt[1].fail = 1; pt[0].fail_len = 2; pt[1].fail_len = 1; } int add(int c, int n) { int p = lst; ss[n] = c + 'a'; while (ss[n - pt[p].len - 1] != ss[n]) p = pt[p].fail; if (!pt[p].go[c]) { int v = ++tot, k = pt[p].fail; pt[v].len = pt[p].len + 2; while (ss[n - pt[k].len - 1] != ss[n]) k = pt[k].fail; pt[v].fail = pt[k].go[c]; pt[v].fail_len = pt[pt[v].fail].fail_len + 1; pt[p].go[c] = v; } return lst = pt[p].go[c]; } ll r[N], ans; int lens; int main() { scanf("%s", s + 1); lens = strlen(s + 1); build(); for (int i = 1; i <= lens; i++) { r[i] = (pt[add(s[i] - 'a', i)].fail_len - 2) + r[i - 1]; } // cout<< endl; memset(pt, 0, sizeof(pt)); build(); for (int i = lens; i > 1; i--) { ans += (pt[add(s[i] - 'a', lens - i + 1)].fail_len - 2) * r[i - 1]; } cout << ans; return 0; }