Western Subregional of NEERC, Minsk, Wednesday, November 4, 2015 Problem G. k-palindrome dp

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;
}
上一篇:Python SMTP发送邮件Ⅱ


下一篇:python SMTP 发送邮件 阿里企业邮箱、163邮箱 及535错误