字符串--最长回文子串（暴力讲解+Manacher）

问题描述：给你一个字符串str，若子串s是回文串，则称s为str的回文子串，求s的最大长度

解法一：暴力匹配

              对每一个字符，假定位置为i,匹配判断i+1与i-1位置是否相等，相等ans长度加一,否则停止。

        

              对奇数，ans=1；对偶数，ans初始为0.（不知道奇数偶数，两种都要写，最后取较大值）。奇数偶数都要判断，代码很长，复杂度O(（2*N+1）*N)=O(N^2).

              比起一般暴力三方快一点。

解法二：Manacher

     严格复杂度O（N）       

     step1:预处理，将奇偶变为奇数。

             对于一个串str长度为n，有n-1个空格，首位有两个，对这些空处理，长度变成2n+1。

 

     可以加str中不存在的东西，比如#。

             step2: 构造数组p[n]

            数组p[i]来记录字符串s[i]最长回文串向左向右扩张p[i]长度的最大值。

         

     如图，对应的关系，p[i]-1正好是原字符串最长回文子串的长度。

     如何求p[i]数组？

      求p[i]时，p[1]....p[n]是已知的。

      对任意位置i,可以扩张的范围是i±p[i]，这个范围都是回文的。对于k+p[k](k=1,2,.....i-1)有最大值记为mx,有一个id（id的值就是前面mx取得最大值对应的p[k]的k的值），

     i关于id的位置是 j  (j=2*id-i),mx关于id对称点是my (my=2*id-mx).

     那么，从id两侧（从my到mx）一定是回文的。

    如果i+p[j]长度在mx之内就取它，如果i+p[j]长度不可控，在mx之外，就取mx-i

    总之取  p[i]=min(p[2*id-i],mx-i)

                     没有可利用的p[i]=1；接下来该怎样就怎样。

 

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char s[10000],s2[100000];
int p[10000];
int size;
void Manacher(char *s,int * p)
{
	 size=strlen(s);
	p[0]=1;
	int id=0;
	int mx=1;
	for(int i=1;i<size;i++)
	{
		if(mx>i)
		{
			p[i]=min(p[2*id-i],mx-i);
		}
		else
		{
			p[i]=1;
		}
		for(;s[i+p[i]]==s[i-p[i]]&&(i-p[i]>=0);p[i]++);
		if(mx<i+p[i])
		{
			mx=i+p[i];
			id=i;
		}
	}
	
} 

int main()
{
	while(1)
	{
	scanf("%s",s2);
	size=strlen(s2);
	
	for(int i=0;i<2*size+1;i++)
	{
		s[i]='#';
		s[++i]=s2[i/2];
	}
printf("%s\n",s);
	Manacher(s,p);

for(int i=0;i<size;i++) 
	printf("%d%c",p[i]-1," \n"[i==size-1]); 
    }
}