L2-008 最长对称子串 （25 分）

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

输入格式：

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

输出格式：

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

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

 

从两端往中间找回文串，找到的第一个回文串一定是最长的。这实际上是一种经典算法：马拉车算法

 代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

int main()
{
	int n,i,j,l,r,flag,Max=-inf;
	string a;
	getline(cin,a);
	n=a.length();
	for(i=0;i<n;i++)
	{
		for(j=n-1;j>=0;j--)
		{
			if(a[j]==a[i])
			{
				l=i;r=j;
				flag=1;
				while(l<=r)
				{
					if(a[l]!=a[r])
					{
						flag=0;
						break;
					}
					l++;r--;
				}
				if(flag)
				Max=max(Max,j-i+1);
			}
		}
	}
	cout<<Max<<endl;
	return 0;
}