HDU - 5658 CA Loves Palindromic（回文自动机）

题意：

求区间内所有本质不同的回文串的数量

题解：

水题，枚举后缀记录即可

$AC$代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int MAXN = 1050; const int INF = 0X3f3f3f3f; const int MOD = 51123987; char s[MAXN]; int n; struct Trie{ int nxt[MAXN][26],fail[MAXN],len[MAXN]; int sz,lst,sn; char str[MAXN]; inline void Init(){ memset(nxt,0,sizeof(nxt)); memset(fail,0,sizeof(fail)); memset(len,0,sizeof(len)); fail[0] = fail[1] = 1; len[0] = 0,len[1] = -1; sz = lst = 1; str[0] = '#'; sn = 0; } inline void Insert(char ch){ str[++sn] = ch; int root = lst; while(str[sn]!=str[sn-len[root]-1]) root=fail[root]; if(!nxt[root][ch-'a']){ len[++sz] = len[root] + 2; int tmp = fail[root]; while(str[sn]!=str[sn-len[tmp]-1]) tmp=fail[tmp]; fail[sz] = nxt[tmp][ch-'a']; nxt[root][ch-'a'] = sz; } lst = nxt[root][ch-'a']; } }PAM; int f[MAXN][MAXN]; inline void solve(){ for(int i=1;i<=n;i++){ PAM.Init(); for(int j=i;j<=n;j++){ PAM.Insert(s[j]); f[i][j] = PAM.sz-1; } } } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s",s+1); n = strlen(s+1); int Q,l,r; scanf("%d",&Q); solve(); while(Q--){ scanf("%d%d",&l,&r); printf("%d\n",f[l][r]); } } return 0; }