PAT 甲级 1040 Longest Symmetric String (25 分)（字符串最长对

发布时间：2020-12-14 00:43:08 所属栏目：Linux 来源：网络整理

导读：1040?Longest Symmetric String?(25?分) ? Given a string,you are supposed to output the length of the longest symmetric sub-string. For example,given? Is PATTAP symmetric? ,the longest symmetric sub-string is? s PATTAP s ,hence you must outp

1040?Longest Symmetric String?(25?分)

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.

Input Specification:

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

Output Specification:

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

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

题意：

输入一个字符串，求该字符串中最长对称子串的长度。

题解：

穷举搜索，既要考虑? baab这种偶数类型的，也要考虑abcba这种技术类型的。

AC代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<cstring>
using namespace std;
string a;
int main(){
    getline(cin,a);
    int len=a.length();
    int mx=1;
    //先偶数
    int r=0,l=1;
    int k;
    for(r=0;r<len;r++)
    {
        l=r+1;
        k=0;
        int rr=r;
        int ll=l;
        while(rr>=0&&ll<len&&a[rr]==a[ll]){
            k+=2;
            rr--;ll++;
        }
        mx=max(k,mx);
    }
    //再奇数
    for(r=0;r<len;r++)
    {
        l=r+2;
        k=1;
        int rr=r;
        int ll=l;
        while(rr>=0&&ll<len&&a[rr]==a[ll]){
            k+=2;
            rr--;ll++;
        }
        mx=max(k,mx);
    }
    cout<<mx<<endl;
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!