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;
			}
		}
	}
}

整體代碼