【Description】
给你一个字符串;
让你在其中找到1..k阶的回文子串;
并统计它们的数量
如果一个字符串是一个回文串,则它可以是1阶子串;
k阶字符串,要求它的左边和右边都是k-1阶子串;
bo[i][j]表示i..j这一段是否为回文;
可以用
然后
算出这个区间的字符串最大可以是一个几阶字符串记为k;
ans[k]++;
如何算?
递归!
void getk(int l,int r)
如果l..r这一段不是回文,则直接返回0;
可以认为他是”0”阶子串;
如果l..r这一段是回文;
那么就只要在l..mid和mid..r这两段中选一段;
再递归求它的字符串阶数+1就好了;
不用两个都算!
则这里复杂度为
总的复杂度为
最后;
阶数为i的字符串也被认为是阶数为1..i的字符串;
所以
for (int i = n-1;i >= 1;i–)
ans[i]+=ans[i+1];
2
我一开始,想的是,从低阶的字符串推出高阶的字符串
没有考虑到,这样增长得是很快的;
竟然没有想到逆向..
#includeusing namespace std; const int N = 5e3; char s[N+10]; int n,bo[N+10][N+10],ans[N+10]; //int dp[N+10][N+10]; int getk(int l,int r){ if (!bo[l][r]) return 0; if (l==r) return 1; if (l+1==r) return 2; int len = (r-l+1)/2; int L = l,R = r; return getk(L,L+len-1)+1; } int main(){ // memset(dp,255,sizeof dp); scanf("%s",s+1); n = strlen(s+1); for (int i = 1;i <= n;i++){ bo[i][i] = 1; if (i+1 <= n && s[i]==s[i+1]) bo[i][i+1] = 1; } for (int i = 3;i <= n;i++){ for (int j = 1;j <= n;j++){ int r = j + i - 1; if (r > n) break; if (bo[j+1][r-1] && s[j]==s[r]) bo[j][r] = 1; } } for (int i = 1;i <= n;i++) for (int j = i;j <= n;j++){ ans[getk(i,j)]++; } for (int i = n-1;i >= 1;i--) ans[i]+=ans[i+1]; for (int i = 1;i <= n;i++) printf("%d ",ans[i]); return 0; }