Codeforces #427 Div2 D

#427 Div2 D

题意

给出一个字符串，求它的子串中为 \(k-palindrome\) 的个数。

\(1-palindrome\) 要求是一个回文串。

\(k-palindrome (k > 1)\)满足以下条件：

• 是一个回文串
• 它的左右两边是一个不为空的 \((k - 1)-palindromes\) 。

分析

求字符串回文子串个数是一个很经典的题目了，这题变化也不大。

\(dp[i]\) 表示以当前字符结尾的长度为 \(i\) 的字符串 \(k\) 的最大值。

注意 \(2-palindrome\) 同时也是 \(1-palindrome\) 。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

char s[5005];

int dp[5005];

int ans[5005];

int main() {

    scanf("%s", s + 1);

    int len = strlen(s + 1);

    int sum = 0;

    vector<int> v1, v2;

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

        ans[1]++; ans[2]--;

        v2.push_back(1);

        dp[1] = 1;

        if(s[i] == s[i - 1]) {

            v2.push_back(2);

            ans[1]++; ans[2]--;

            ans[2]++; ans[3]--;

            dp[2] = 2;

        }

        for(int j = 0; j < v1.size(); j++) {

            int l = v1[j];

            if(s[i - l - 1] == s[i]) {

                v2.push_back(l + 2);

                dp[l + 2] += dp[l / 2 + 1] + 1;

                ans[1]++; ans[dp[l + 2] + 1]--;

            }

        }

        memset(dp, 0, sizeof dp);

        v1 = v2;

        v2.clear();

    }

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

        ans[i] += ans[i - 1];

    }

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

        printf("%d%c", ans[i], " \n"[i == len]);

    }

    return 0;

}