A1040 Longest Symmetric String (25 point(s))

最长回文子串

1. 原文

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:

11

2. 解析

3. AC代码

#include<iostream>
#include<string>
using namespace std;
int dp[1010][1010];
int main()
{
    string str;
	getline(cin,str);
	int ans=0;
    int len=0;
    for (int i = 0; i < str.length(); ++i)
    {
        len++;
    	dp[i][i]=1;
    	ans=1;
    }
    for (int i = 0; i < str.length() -1 ; ++i)
    {
    	if (str[i]==str[i+1])
    	{
    		dp[i][i+1]=1;
    		ans=2;
    	}
    }
	for (int L = 3; L<= len ; ++L){
		for (int i = 0; L+i-1 <len ; ++i){
			int j=L+i-1;
			if (str[i]==str[j]&&dp[i+1][j-1]==1){
				dp[i][j]=1;
				ans=L;
			}
		}
	}
    cout<<ans<<endl;
	return 0;
}