CF1827C
此题要求 \(S\) 中美丽子串的数量。考虑枚举每个美丽子串的起始点为 \(i\)，因为大回文串可以分解成小回文串，所以提前处理记录以每个点 \(i\) 为起点的最小回文串大小为 \(nxt_i\)。然后以 \(i\) 为起点扩展到 \(i+nxt_i\)，然后递归处理到 \(i > n\) 后返回回文串数量 \(Ans_i\) 。答案即为 \(\sum\limits_{i=1}^{n} Ans_i\)。因为最多可能有 \(n^2\) 个美丽子串，所以要记忆化处理保证复杂度为 \(O(n)\) 。
int dfs(int j){if(j>n*2) return 0;if(ans[j]!=0) return ans[j];ans[j]=dfs(j+nxt[j]+2)+1;return ans[j];
}
nxt数组计算过程：
void manacher(){int l=0,r=-1,cnt=0,sum=0;for(int i=1;i<=2*n;i+=2){if(i>r){for(int j=i;j<=n*2;j++){if(i*2-j<0) break;if(s[i*2-j]==s[j]){nxt[i*2-j]=min(nxt[i*2-j],j*2-i*2);pre[j]=min(pre[j],j*2-i*2);d2[i]=j-i;}else break;}if(i+d2[i]>=r){r=i+d2[i];l=i-d2[i];cnt=i;}}else{d2[i]=min(d2[cnt*2-i],r-i);if(cnt*2-i+1-pre[cnt*2-i+1]>l) nxt[i-1]=min(pre[cnt*2-i+1],nxt[i-1]);int tmp=i+min({d2[i],i-cnt,i-sum}); //复杂度瓶颈，最优性减枝for(int j=i+1;j<=tmp;j+=2){nxt[i*2-j]=pre[cnt*2+j-i*2];pre[j]=nxt[cnt*2-j];}for(int j=i+d2[i];j<=n*2;j++){if(i*2-j<0) break;if(s[i*2-j]==s[j]){nxt[i*2-j]=min(nxt[i*2-j],j*2-i*2);pre[j]=min(pre[j],j*2-i*2);d2[i]=j-i;}else break;}if(d2[i]>=i-cnt) sum=i;if(i+d2[i]>=r){ //复杂度瓶颈，靠更新左端点优化计算r=i+d2[i];l=i-d2[i];cnt=i;}}}
}
整体代码