本文共 1628 字，大约阅读时间需要 5 分钟。

1154 回文串划分

题目

有一个字符串S，求S最少可以被划分为多少个回文串。

a|bb|aabaa - 3 个回文串

其中第1种划分方式的划分数量最少。

输入

输入字符串S(S的长度<= 5000)。

输出

输出最少的划分数量。

输入样例

abbaabaa

输出样例

3

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 3e5;char s[maxn], str[maxn];// 初始长度，处理后长度int len1, len2;// 所有值，最大值int p[maxn], ans;// dp[i]：前 i 个数最少能变几个回文int dp[maxn];void init() {
       str[0] = '(';    str[1] = '#';    for (int i = 0; i < len1; i++) {
           str[i * 2 + 2] = s[i];        str[i * 2 + 3] = '#';    }    len2 = len1 * 2 + 2;    str[len2] = ')';}void manacher() {
       int id = 0, mx = 0;    for (int i = 1; i < len2; i++) {
           if (mx > i) p[i] = min(p[2 * id - i], mx - i);        else p[i] = 1;        while (str[i + p[i]] == str[i - p[i]])            p[i]++;        if (p[i] + i > mx) {
               mx = p[i] + i;            id = i;        }    }}int main() {
       while (scanf("%s", s) != EOF) {
           len1 = strlen(s);        init();        manacher();        ans = 0;        for (int i = 0; i < len1; i++) {
               dp[i] = i + 1;            int pos = (i + 1) * 2;            for (int j = pos; j >= 1; j--) {
                   if (j + p[j] - 2 >= pos) {
                       int pre = (j - (pos - j)) / 2 - 1;                    if (pre == 0) {
                           dp[i] = 1;                    } else {
                           dp[i] = min(dp[pre - 1] + 1, dp[i]);                    }                }            }        }        printf("%d\n", dp[len1 - 1]);    }}
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108277580 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！