1040. Longest Symmetric String (25)

淡淡的烟草味﹌ 2022-05-31 10:48 113阅读 0赞

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:**

--------------------

题目大意：

给定一个字符串，你应该输出最长对称字符串的长度。例如，给定"Is PAT&TAP symmetric?"，因此你必须输出11.  
输入规格：  
数个输入文件包含一个测试用例，该测试用例的长度不超过1000.  
输出规范：  
对于每个测试用例，只需在一行中打印最大的长度。

代码：

解法一：

#include<string>
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    int main()
    {
        int i,j,n,m,k,t,Max=1;
        string s;
        getline(cin,s);
        for(i=0;i<s.size();i++)
        {
            if(s.size()-i<=Max)
                break;
            for(j=i;j<s.size();j++)
            {
                string str1,str2;
                str1=s.substr(i,j+1);
                str2=str1;
                reverse(str1.begin(),str1.end());
                if(str1==str2)
                {
                    if(str1.size()>Max)
                    {
                        Max=str1.size();
                    }
                }
    
            }
        }
        printf("%d\n",Max);
        return 0;
    }

解法二：

#include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int dp[1010][1010];
    int main()
    {
        string str;
        int i,j,m,k,t;
        getline(cin,str);
        fill(dp[0],dp[0]+1010*1010,1);
        int n=str.length();
        //printf("%d\n",n);
        int Max=1;
        for(i=0;i<n-1;i++)
        {
            if(str[i]==str[i+1])
                {
                    dp[i][i+1]=1;
                    Max=2;
                }
                else
                {
                   dp[i][i+1]=0;
                }
        }
        for(i=2;i<n;i++)
        {
            for(j=0;j+i<n;j++)
            {
                    if(str[j]==str[j+i]&&dp[j+1][j+i-1]!=0)
                    {
                        //printf("%c %c\n",str[j],str[j+i]);
                        dp[j][j+i]=1;
                        Max=i+1;
                    }
                    else
                    {
                        dp[j][j+i]=0;
                    }
            }
        }
        printf("%d\n",Max);
        return 0;
    }