比赛地址：Codeforces Round #427 (Div. 2)

D. Palindromic characteristics

题意：

当一个字符串满足满足下列要求的时候它是k回文串。 1、左半边和右半边相等 2、左右都是非空k-1回文串

给定一个串，求各种回文串的数量。

思路

两种思路： 第一种： 上面的条件可以推断出： 对于串s[l][r] 1、s[l][r]是回文串 2、左右都是k-1回文串 进一步： 1、s[l] = s[r] s[l-1][r-1]回文 2、dp[l][r] = dp[l][mid] + 1 第二种解法： 对一个串，我们可以用hash的方法在o1的时间内来判断两个串是否相等，所以直接根据题意dp即可。

代码：

第一种解法的代码：

#include <bits/stdc++.h> using namespace std; const int N = 5005; string s; int n; short dp[N][N]; int ans[N]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> s; n = (int) s.size(); for (int len = 1; len <= n; len++) { for (int l = 0; l < n - len + 1; l++) { int r = l + len; if (len == 1) { dp[l][r] = 1; continue; } else if (len == 2) { dp[l][r] = (s[l] == s[r - 1] ? 2 : 0); continue; } if (s[l] != s[r - 1] || !dp[l + 1][r - 1]) { continue; } dp[l][r] = 1; int m = (l + r) / 2; if (len & 1) { if (dp[l][m] && dp[m + 1][r]) { dp[l][r] = dp[l][m] + 1; } } else { if (dp[l][m] && dp[m][r]) { dp[l][r] = dp[l][m] + 1; } } } } for (int len = 1; len <= n; len++) { for (int l = 0; l < n - len + 1; l++) { ans[dp[l][l + len]]++; } } for (int i = n - 1; i >= 1; i--) { ans[i] += ans[i + 1]; } for (int i = 1; i <= n; i++) { cout << ans[i] << " "; } cout << "\n"; return 0; }

第二种解法的代码：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> using namespace std; const int MAXN = 5010; const unsigned long long SEED = 13331; unsigned long long P[MAXN]; unsigned long long S[MAXN]; unsigned long long RS[MAXN]; int dp[MAXN][MAXN]; int ans[MAXN]; string s; int n; unsigned long long HS( int l, int r ){ if( l == r ){ return s[l]; } l++; r++; return S[r] - S[l-1] * P[r-l+1]; } unsigned long long RHS( int l, int r ){ if( l == r ){ return s[l]; } l = n - l - 1; r = n - r - 1; swap( l, r ); l++; r++; return RS[r] - RS[l-1] * P[r-l+1]; } int DFS( int l, int r ){ if( l == r ){ return dp[l][r] = 1; } if( dp[l][r] != -1 ){ return dp[l][r]; } int ll = ( l + r - 1 ) / 2; int rr = ( l + r ) / 2 + 1; if( RHS( l, r ) == HS( l, r ) ){ dp[l][r] = 1; }else{ dp[l][r] = 0; } if( HS( l, ll ) == HS( rr, r ) ){ dp[l][ll] = DFS( l, ll ); dp[rr][r] = DFS( rr, r ); if( dp[l][ll] && dp[rr][r] ){ dp[l][r] = min( dp[l][ll], dp[rr][r] ) + 1; } } return dp[l][r]; } int main(){ cin >> s; P[0] = 1; for( int i = 1; i < MAXN; i++ ){ P[i] = P[i-1] * SEED; } n = s.size(); for( int i = 1; i <= n; i++ ){ S[i] = S[i-1] * SEED + s[i-1]; } for( int i = 1; i <= n; i++ ){ RS[i] = RS[i-1] * SEED + s[n-i]; } memset( dp, -1, sizeof( dp ) ); for( int i = 0; i < n; i++ ){ for( int j = i; j < n; j++ ){ dp[i][j] = DFS( i, j ); } } memset( ans, 0, sizeof( ans ) ); for( int i = 0; i < n; i++ ){ for( int j = i; j < n; j++ ){ ans[dp[i][j]]++; } } for( int i = n - 1; i >= 1; i-- ){ ans[i] += ans[i+1]; } printf( "%d", ans[1] ); for( int i = 2; i <= n; i++ ){ printf( " %d", ans[i] ); } puts(""); return 0; }