[动态规划] 回文子串_回文子串 动态规划

回文子串

题目描述

给定一个字符串，输出所有回文子串。
回文子串即从左往右输出和从右往左输出结果是一样的字符串
比如： abba   cccdeedccc都是回文字符串
我们要查找的子串长度应该大于等于2

关于输入

输入是一行，即可一个字符串。长度500以内
比如：
abcddcbaab

关于输出

输出所有的回文子串，一个满足条件的子串一行。
子串长度小的优先输出，出现在原始字符串靠左的子串优先输出。
比如对于abcddcbaab
输出：
dd
aa
cddc
baab
bcddcb
abcddcba

例子输入

123321125775165561

例子输出

33
11
77
55
2332
2112
5775
6556
123321
165561

解题分析

首先，我们可以定义一个二维数组dp，它的大小是501x501，所有元素都初始化为0。在这个数组中，dp[i][j]表示从位置i到位置j的子串是否是回文。

接下来我们可以设置两层循环：

这个循环是程序的核心部分。外层的循环变量l表示子串的长度，从2开始，一直到字符串的长度len。内层的循环变量i表示子串的开始位置，从0开始，一直到len-l，末尾位置j我们设为i+l-1（例如i=0，l=2表示从0位置开始的长度为2的子串，即str[0]和str[1]，1=0+2-1）。

在内层的循环中，我们首先计算子串的结束位置j（即i+l-1）。然后，我们检查子串的开始和结束位置的字符是否相同，并且子串去掉两端之后的部分（即从i+1到j-1的部分）是否是回文。如果这两个条件都满足，那么我们就知道从i到j的子串是回文，于是我们将dp[i][j]设为1，并打印出这个子串。

在打印子串的代码中，我们使用了一个循环来打印出子串的所有字符，然后打印一个换行符，表示这个子串的结束。

经指正，应该注意到每一个长度为1的子串都应该视为回文子串，故循环代码中应该加上dp[i][i]=1，不然无法输出奇数长度的子串。

代码实现

#include <stdio.h>
#include <string.h>
 
int main() {
    char str[501];
    scanf("%s", str);
 
    int len = strlen(str);
    int dp[501][501] = {0};
 
    for (int l = 2; l <= len; l++) {
        for (int i = 0; i + l - 1 < len; i++) {
            dp[i][i]=1;
            int j = i + l - 1;
            if (str[i] == str[j] && (l == 2 || dp[i + 1][j - 1])) {
                dp[i][j] = 1;
                for (int k = i; k <= j; k++) {
                    printf("%c", str[k]);
                }
                printf("\n");
            }
        }
    }
 
    return 0;
}

（方法2）

当然，如果我们使用c++的string类型，本题将会变得非常简单，不再需要动态规划也能较为迅速的做出。

#include <iostream>
using namespace std;
 
bool iscyclic(string s){
    for(int i=0,j=s.size()-1;i<=j;i++,j--){
        if(s[i]!=s[j]) return 0;
    }
    return 1;
}
 
int main() {
    string s; cin>>s;
    for(int i=2;i<=s.size();i++){
        for(int k=0;k<=s.size()-i;k++){
            string temp=s.substr(k,i);
            if(iscyclic(temp)){
                cout<<temp<<endl;
            }
        }
    }
    return 0;
}

这个程序的目标也是找出一个字符串中的所有回文子串。这个程序使用了一个不同的方法，即直接生成所有可能的子串，然后检查每个子串是否是回文。

以下是程序的详细思路：

1. **定义回文检查函数**：首先，程序定义了一个名为`iscyclic`的函数，用于检查一个字符串是否是回文。这个函数通过比较字符串的两端的字符来工作：如果两端的字符都相同，那么它就继续检查下一对字符，否则它就返回0，表示这个字符串不是回文。如果所有的字符对都相同，那么函数就返回1，表示这个字符串是回文。

2. **输入字符串**：在`main`函数中，程序首先读取一个字符串，存储在变量`s`中。

3. **生成子串**：接下来，程序开始生成所有可能的子串。外层循环的变量`i`表示子串的长度，从2开始，一直到字符串的长度。内层循环的变量`k`表示子串的开始位置，从0开始，一直到`s.size()-i`。这样可以保证子串的结束位置不超过字符串的长度。

   - 在内层的循环中，程序使用`substr`函数生成一个子串，然后使用`iscyclic`函数检查这个子串是否是回文。

4. **输出回文子串**：如果找到一个回文子串，程序就直接打印出这个子串。

关于`substr`函数，它是C++的`string`类的一个成员函数，用于生成一个字符串的子串。`substr`函数接受两个参数：第一个参数是子串的开始位置，第二个参数是子串的长度。例如，`s.substr(k, i)`生成了从位置`k`开始，长度为`i`的子串。

这就是这个程序的全部思路。这个程序的关键是直接生成所有可能的子串，然后检查每个子串是否是回文。