5-12 最长对称子串   (25分)

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

解法一：暴力方法---从外往里

对每一个字符，从该字符往右走，同时从串的结尾往中间走。若相遇，则对称；否则，不对称。复杂度O(n3)

解法二：从里往外

从里向外来判断，也就是我们先判断子字符串A是不是对称的。如果A不是对称的，那么向该子字符串两端各延长一个字符得到的字符串肯定不是对称的。如果A对称，那么我们只需要判断A两端延长的一个字符是不是相等的，如果相等，则延长后的字符串是对称的。因此在知道A是否对称之后，只需要O（1）的时间就能知道aAa是不是对称的。复杂度为O(n3)


 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int maxlen = 0;
void LPS(const string &str)//从头到尾三重循环
{   int i,j;
    int len = str.length();
    for(i=0;i<len;i++)
    {
        for(j=len-1;j>=i;j--)
        {
            if(str[i]==str[j])
            {
                int start,end;
                for(start =i,end =j;start<=end;start++,end--)
                if(str[start]!=str[end])
                {
                    break;
                }
                if(end<=start)
                maxlen = max(maxlen,j-i+1);
            }
        }
    }
}
int LPSS(const string &str)//从中间向外扩展
{
    if(str.size()==0)
    return 0;
    int ret = 0;
    int len = str.length();
    for(int i=0;i<len;i++)
    {
        /*子字符串长度为奇数*/
        int low = i-1;
        int high =i+1;
        while(low>=0&&high<len&&str[low]==str[high])
        {
            low--;
            high++;
        }
        int tmp = high-low-1;
        if(tmp>ret)
        ret = tmp;
        /*子字符串长度为偶数*/
        low = i;
        high = i+1;
        while(low>=0&&high<len&&str[low]==str[high])
        {
        low--;
        high++;
        }
        tmp = high-low-1;
        if(tmp>ret)
        ret = tmp;
    }
    return ret;
}
int main()
{
    char str[1002];//注意string定义加cin输入无法读入空格
    gets(str);
    maxlen = LPSS(str);
    cout<<maxlen<<endl;
    return 0;
}


解法三：动态规划 O(n2)
X[i]==X[j] && dp[i+1][j-1]==1 则dp[i][j] = 1

#include <iostream>
#include <string>
using namespace std;

#define N 100

bool dp[N][N];
int maxLen;

void LPS(const string &str)
{
	int strLen = str.length();

	for (int i=0; i<strLen; i++)
	{
		dp[i][i] = 1;
		if (i>0 && str[i]==str[i-1])
			dp[i-1][i] = 1;
	}

	for (int len=2; len<=strLen; len++)
	{
		for (int i=0; i<strLen-len+1; i++)
		{
			int j = i + len;

			if ((str[i]==str[j]) && (dp[i+1][j-1]==1))
			{
				dp[i][j] = 1;
				if (j-i+1>maxLen)
					maxLen = j-i+1;
			}
		}
	}
	
}

int main()
{
	string str;

	cin>>str;

	LPS(str);

	cout<<maxLen<<endl;

	return 0;
}