Problem G. k-palindrome

题目连接：

http://opentrains.snarknews.info/~ejudge/team.cgi?SID=c75360ed7f2c7022&all_runs=1&action=140

Description

We will say that a string T is a k-palindrome for some positive integer k if and only if k is not grater than

the length of T and its prefix of the length k is equal to the reversed suffix of that length. For example,

abacaba is a k-palindrome for any k from 1 to 7 while abacabada is only 1-palindrome.

You are given a string S. Try to find the number of k-palindrome substrings of S for all k from 1 to the

length of S.

Input

The only line of input contains the string S (1 ≤ |S| ≤ 5000). The string contains only lowercase letters

of the Latin alphabet.

Output

Output |S| integers, the kth of them should be equal to the number of k-palindrome substrings of S.

Sample Input

abacaba

Sample Output

14 5 5 2 2 1 1

Hint

题意

k回文串就是表示这个串的前k个字符和后k个字符是回文的。

然后给你一个人串，问你他的k回文子串有多少个，k从1到n

题解：

首先k回文串的话，那么他一定是k-1回文串，所以只要知道最长的就好了。

枚举起点枚举终点，hash二分，这个复杂度n^2logn

但是可以n^2，就用dp去预处理起点和终点的最长前后缀，这个傻逼dp就好了。

代码

#include <bits/stdc++.h>

#define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))

#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))

#define pb push_back

#define mp make_pair

#define sf scanf

#define pf printf

#define two(x) (1<<(x))

#define clr(x,y) memset((x),(y),sizeof((x)))

#define dbg(x) cout << #x << "=" << x << endl;

const int mod = 772002;

int mul(int x,int y){return 1LL*x*y%mod;}

int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

using namespace std;

const int maxn = 5000 + 50;

int f[maxn][maxn],len,ans[maxn];

char str[maxn];

int DFS(int l , int r){

    if(~f[l][r]) return f[l][r];

	if(l>len||r<=0) return f[l][r]=0;

	if(str[l]==str[r]) f[l][r] = DFS(l+1,r-1)+1;

	else f[l][r] = 0;

	return f[l][r];

}

int main( int argc , char * argv[] ){

	//freopen("in.txt","r",stdin);

	sf("%s",str+1);

	len=strlen(str+1);

	memset(f,-1,sizeof(f));

	for(int i = 1 ; i <= len ; ++ i) for(int j = i ; j <= len ; ++ j) ans[min(j-i+1,DFS(i,j))]++;

	for(int i = len ; i >= 1 ; -- i) ans[i - 1] += ans[i];

	for(int i = 1 ; i <= len ; ++ i){

		if( i > 1 ) pf(" ");

		pf("%d",ans[i]);

	}

	pf("\n");

	return 0;

}