2021秋季《数据结构》_EOJ.1040 最长回文子串

题目

一个字符串如果从左往右和从右往左读的结果是一样的，则称为回文字符串。写程序找出给定字符串的最长回文子串。例如字符串 abcbabcb，有多个回文字串 bcb，bab，cbabc，bcbabcb 等，其中最长回文子串为 bcbabcb。

思路

方法1

二维数组dp，a[i][j]表示s[i]~s[j]是否为回文串，状态转移方程
$$a[i][j]=\{\begin{array}{ll}0,& s[i]!=s[j]\\ a[i+1][j?1],& s[i]==s[j]\end{array}$$
注意

• 将i==j处初始化为1，因为字符本身构成长度为1的回文串
• 只需遍历j > i的部分
• 特殊讨论j==i+1，因为此时i+1>j-1

方法2

复习滚动数组

代码

方法1

#include<bits/stdc++.h>
using namespace std;int main()
{
    int t; cin>>t;for(int i = 0; i < t; i++){
    string s; cin>>s;int len = s.length();cout<<"case #"<<i<<':'<<endl;// 申请二维数组int ** a = new int*[len];for(int i = 0; i < len; i++){
    a[i] = new int[len];memset(a[i], 0, sizeof(int)*len);}int res = 1;for(int i = len-1; i >= 0; i--){
    for(int j = i; j < len; j++){
    if(i==j) a[i][j] = 1;else{
    if(s[i]!=s[j]) a[i][j] = 0;else{
    // cout<<"i,j="<<i<<' '<<j<<endl;if(j-i==1){
    a[i][j] = a[i][j-1];}else{
    a[i][j] = a[i+1][j-1];}if(a[i][j])  // 更新res{
    // cout<<"i,j="<<i<<' '<<j<<endl;if(j-i+1>res) res = j-i+1;}}}}}// for(int i = 0; i < len; i++)// {
    // for(int j = 0; j < len; j++)// cout<<a[i][j]<<' ';// cout<<endl;// }cout<<res<<endl;// 释放数组空间for(int i = 0; i < len; i++){
    delete[] a[i];}delete []a;}system("pause");return 0;
}

方法2

同样注意从右向左遍历（注意点已在注释中标注）

#include<bits/stdc++.h>
using namespace std;int main()
{
    int t; cin>>t;for(int i = 0; i < t; i++){
    string s; cin>>s;int len = s.length();cout<<"case #"<<i<<':'<<endl;int* a = new int[len];memset(a, 0, sizeof(int)*len);int res = 1;for(int i = len-1; i >= 0; i--){
    for(int j = len-1; j >= i; j--){
    if(i==j) a[i] = 1;else{
    if(s[i]!=s[j]) a[j] = a[i];else{
    if(j==i+1) a[j] = 1;// if(j==i+1)// {
    // a[j] = a[j-1];// } // 错误，因为滚动数组从右到左更新，// 此时a[j-1]还没有被更新else{
    a[j] = a[j-1];}if(a[j]){
    if(res<j-i+1) res = j-i+1;}}}}// for(int k = 0; k < len; k++)// cout<<a[k]<<' ';// cout<<endl;}delete[] a;cout<<res<<endl;}system("pause");return 0;
}