最长回文子串
hihocoder 的一道题目，说是很经典的题目，但是自己还没做过，看来非ACMer差距还是巨大的。。
然后自己搞了半天也只搞出了O(n^2)的算法，看了一下线性算法，太复杂了，本吊估计是想不出了。
附上O(n^2)的基于移动中心的算法
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <sstream>
#include <iomanip>
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
using namespace std;
int maxdrome(string str)//O(n^3)
{
int maxlen=1;
for(int length=2;length<=str.size();length++)//length
{
for(int i=0;i<=str.size()-2;i++)//start index
{
//for(int j=i+1;j<=n-1;j++)
//{
if(i+length-1>=str.size()) continue;
int k;
for(k=0;k<length/2;k++)
{
if(str[i+ k]==str[i+length-1 - k])
;
else
break;
}
if(k==length/2)
{
if(maxlen<length)
maxlen=length;
}
//}
}
}
return maxlen;
}
int maxdrome_centre(string str)
{
if(str.size()==0) return 0;
int maxlen=1,max;
for(int i=1;i<str.size()-1;i++)
{
max=1;
for(int j=1;j<=(str.size()-1)/2;j++)//two
{
if(i-j>=0 && i+j <=str.size()-1)
{
if(str[i-j] == str[i+j])
max+=2;
else
break;
}
else
break;
}
if(max>maxlen)
maxlen=max;
max=1;
if(str[i]==str[i+1])
{
max++;
for(int j=1;j<=(str.size()-2)/2;j++)
{
if(i-j>=0 && i+1+j<=str.size()-1 )
{
if(str[i-j]==str[i+1+j])
max+=2;
else
break;
}
else
break;
}
if(max>maxlen)
maxlen=max;
}
}
return maxlen;
}
int main()
{
//read;
//write;
int n;
//cin.clear();
//cin>>n;
//cin.clear();
scanf("%d",&n);
string str;
//cin>>str;
getline(cin,str);
while(n>0)
{
getline(cin,str);
//if(str.size()==0)
// break;
cout<<maxdrome_centre(str)<<endl;
n--;
}
return 0;
}
我当时还请教了高富帅，发现他好像也没有想出线性算法，关键是里面有个推导出了一个不等式性质，
P[i] >= MIN(P[2 * id - i], mx - i)
线性算法是基于这个不等式的，数学不够屌是搞不出来的，或者之前做过，我现在也没完全理清楚这个头绪，咳。。。
之前写了一个O(n^3) O(n^2)的算法，感觉很像是最长字段和从n^3 一直杀到线性，正如Lucida所说大为所快，但是最后线性的其实
不算是DP，我也没搞出来。。
http://blog.163.com/zhaohai_1988/blog/static/2095100852012716105847112/
今天看到邹博的PPT，决定这道题目 一定要过掉，包括leetcode上，还有东北大学大一ACMer翟神居然也会，我必须过了。现在完全理解了这个不等式了，P[i]>=Min(P[2id-i],mx-i)
其实本质应该这么理解，如何由P[0..i-1] 推导出P[i], 因为设定三元组 [i,P[i],i+P[i]], mx=k max{k+P[k]}, 0<=k<=i-1 也即最远到的位置的后一个，所以是mx) 开区间，当mx>i的时候，说明可以借助P[0…i-1]里面的最大mx的
那个的mx信息控制i，mx>i 那么基于两次对称性，id(0..i-1最大)对称，以及j(=2id-i)对称, 当mx-i>P[2*id-i=j], P[i]=P[j], 否则，P[i]>=mx-i, 具体等于多少，从延伸出的P[i]两端继续延伸，可能由于计算过操作次数
任然是线性的。
另外记得把原字符串扩展井号，但是如果字符串有井号咋办呢。。。
class Solution {
public:
string longestPalindrome(string s)
{
s=addjing(s);
int n=s.size();
int *P=new int[n];
int id=0,mx=1;
P[0]=1;
for(int i=1;i<n;i++)
{
if(mx>i)
{
if(mx-i>P[2*id-i])
P[i]=P[2*id-i];
else
P[i]=mx-i;
}
else
P[i]=1;
for(;s[i-P[i]]==s[i+P[i]];P[i]++);
if(mx<i+P[i])
{
mx=P[i]+i;
id=i;
}
}
int maxlen=1,maxi=0;
for(int i=0;i<n;i++)
{
if(maxlen<P[i])
{
maxi=i;
maxlen=P[i];
}
}
delete[] P;
string result=s.substr(maxi-maxlen+1,maxlen*2-1);
string newresult="";
for(int i=0;i<(int)result.size();i++)
{
if(result[i]!='#')
newresult+=result[i];
}
return newresult;
}
string addjing(string s)
{
string adds="#";
for(int i=0;i<(int)s.size();i++)
{
adds+=s[i];
adds+='#';
}
return adds;
}
};