[Codeforces] 835D. Palindromic characteristics

題目連結:http://codeforces.com/problemset/problem/835/D

---

先觀察到一件事，是k回文的他一定也是k-1回文，這樣的話就只要知道一個子字串他最大是幾回文就好了，而這可以DP，狀態是$dp[i][j]$代表$i~j$最大可以是幾回文，而轉移也很顯然的就是$dp[i][j] = dp[i][mid]+1$，如果$i~mid == mid~r$的話，否則的話就是0，而要判斷兩個子字串是否相等其實用個hash就好了，只不過我真的不太會寫hash，搞了好久QQ

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 5000 + 5;

class Hash{
	private:
		const lld p = 127, q = 1208220623;
		int sz;
		lld prefix[N], power[N];
	public:
		void init(const string &x){
			sz = x.size();
			prefix[0]=0;
			for(int i=1;i<=sz;i++) prefix[i]=((prefix[i-1]*p)%q+x[i-1])%q;
			power[0]=1;
			for(int i=1;i<=sz;i++) power[i]=(power[i-1]*p)%q;
		}
		lld query(int l, int r){
			// 1-base (l, r]
			return (prefix[r] - (prefix[l]*power[r-l])%q + q)%q;
		}
};

// dp[4][9] : xxxx|jkljk|xxxxx
// [l, r)
int dp[N][N], ans[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	string ss; cin>>ss;
	int n = ss.size();
	Hash ori, rev;
	ori.init(ss);
	reverse(ss.begin(), ss.end());
	rev.init(ss);
	for(int i=0;i<n;i++){
		dp[i][i+1]=1;
		ans[1]++;
	}
	for(int i=2;i<=n;i++){
		for(int l=0;l+i<=n;l++){
			int r = l+i;
			int lmid, rmid;
			if((l+r)&1) lmid=(l+r)>>1, rmid=(l+r+1)>>1;
			else lmid=(l+r)>>1, rmid=(l+r)>>1;
			if(ori.query(l, lmid) == rev.query(n-r, n-rmid)) dp[l][r] = dp[l][lmid]+1;
			else dp[l][r]=0;
			ans[dp[l][r]]++;
		}
	}
	for(int i=n-1;i>=1;i--) ans[i]+=ans[i+1];
	for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
	return 0;
}