//
// main.cpp
// PAT_1040. Longest Symmetric String
//
// Created by wjq on 17/5/7.
// Copyright © 2017年 wjq. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
char c[1005];
int maxLength=0;
int main(int argc, const char * argv[])
{
gets(c);
int length=(int)strlen(c);
for(int i=0;i<length;i++)
{
for(int j=0;i-j>=0&&i+j<length;j++) //奇数字符对称时,j为与i的距离
{
if(c[i-j]!=c[i+j])
break;
if(2*j+1>maxLength)
maxLength=2*j+1;
}
for(int j=0;i-j>=0&&i+1+j<length;j++) //偶数字符对称时,i -j 和i+1 +j都得在范围内.
{
if(c[i-j]!=c[i+1+j])
break;
if(2*j+2>maxLength)
maxLength=2*j+2;
}
}
cout<<maxLength;
return 0;
}
简单枚举一下就好了,其实从中间开始枚举更好,从最长的可能开始算,如果已经算出可能存在的最长了,那么下面的就不用算了(剪枝).
但是考虑到这题字符串最长只有1000个字符,O(N^2)就不会超时了,不需要费劲.
