[C++知识库]c++pta A1040(回文子串)

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given Is PAT&TAP symmetric?, the longest symmetric sub-string is s PAT&TAP s, hence you must output 11.

给定你一个序列，要求你输出最长的回文子序列，比如PAT&TAP symmetric?, 回文，最长的子串s PAT&TAP s，因此你必须输出11

Input Specification:
Each input file contains one test case which gives a non-empty string of length no more than 1000.

输出规格:,每个输入文件包含一个测试样例，给定一个非空不超过1000的字符串。

Output Specification:
For each test case, simply print the maximum length in a line.

对于每个样例，仅仅打印最大的长度在一行里。

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

11

核心思路

确定好对称轴。进行转字符串。

完整代码

#include<iostream>
using namespace std;
int main()
{
    int i,j,k,maxlength = 0;
    string s;
    getline(cin,s);

    for(i = 0;i<s.size();i++){
        for(j =i,k=i;j>=0&&k<s.size()&&s[j]==s[k];j--,k++);
        if(k-j-1>maxlength) maxlength = k-j-1;
    }

    for(i = 0;i+1<s.size();i++){
        for(j=i,k=i+1;j>=0&&k<s.size()&&s[j]==s[k];j--,k++);
        if(k-j-1>maxlength) maxlength = k- j- 1;
    }
    cout << maxlength;
}

方法2

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 1010;
string s;
int dp[maxn][maxn];
int main(){
    getline(cin,s);
    int len = s.length(),ans =1;
    memset(dp,0,sizeof(dp)); //dp数组初始化为0
    //边界
    for(int i =0;i<len;i++){
        dp[i][i] = 1;
        if(i < len-1){
            if(s[i] == s[i+1]){
                dp[i][i+1] = 1;
                ans = 2; //初始化的注意当前最长回文子串的长度
            }
        }
    }
    //状态转移方程
    for(int L= 3;L<=len;L++){//枚举子串的长度
        for(int i = 0;i+L-1<len;i++){//枚举子串的起始断点
            int j = i+L-1; //子串的右端点
            if(s[i] == s[j] && dp[i+1][j-1] ==1){
                dp[i][j] = 1;
                ans = L;//更新最长的回文子串长度
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}