主要是应用在回文串啦，原理也理解了老半天，如果没有图片的话，我也看不太懂它的原理
学习的灵感来源来自于：https://segmentfault.com/a/1190000008484167
/* 最长回文 */
/*给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等 Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000 Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度. Sample Input
aaaa
abab Sample Output
4
3*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
/*说实话我非常讨厌字符串的题目，对于我来说可能是会在输入出现问题，所以我一直都不
太喜欢字符串，拿到这道题是没有什么思路的。但是简单看了解析就不得不佩服他们的想法
他的想法是，在每个字符串之间加入特殊符号，他用的是#，这样子就可以算出奇数个的回
文串了，这样奇数字符串就仍然以字母为中心，偶数字符串就会以#为中心展开，接下来的
方法我还没看，但我可以猜测如果是检索到#的话就隔项去检索字母，如果是检索到字母就
隔项去检索字母，试着去完成一下吧*/
//果然还是以失败告终，我去看看网上的思路吧 char s[], ss[];
int Count[]; int judge( int len )
{
Count[]=;//最低限度是1，但这个点应该用不到的说= =，这句话应该可以删掉
int mx=,id=;
//mx 代表以 id 为中心的最长回文的右边界
for(int i= ; i<=len ; i++ ) //从第一个#开始
{
if( mx>i )//如果这个点包含在右边界之中
{
Count[i] = min( Count[*id-i] , mx-i );
/*这句话简直太精辟了，在id的右边的点i，会等于id左边点的对称点，如果
这个i点到id的点的距离（左段）和i点到mx点的距离（右段）相比，如果右边
比较小，那么就会继续向mx外部检索，如果对称点的Count[2*id-i]还不及边
界，那么就不必继续向外检索了，下面的循环第一步就会停止了*/
}
else
{
Count[i] = ;//如果这个点超出了右边界，那么这个点开始重新计算
}
while( i+Count[i]<=len && ss[i-Count[i]]==ss[ i+Count[i] ] )
Count[i]++;//如果旁边只要有一次相等便会+1，直到不相等为止
if( Count[i]+i > mx )//如果新检索的位置超出了最大边界
{
mx=Count[i]+i;//Count存储的是半径，i是当前位置，相加得新的右边界
id=i;//id记录的是对称点所在位置
}
}
//数据验证
/*for (int i=1 ; i<=len ; i++ )
{
cout<<Count[i]<<' ';
}
cout<<endl;*/
int max=;
for(int i=;i<=len;i++)
{
if( Count[i] > max ) max=Count[i];
}
return max-;
} int main(void)
{
int result;
int j, len, i;
ss[]='$';
ss[]='#';
while ( scanf("%s",s)!=EOF )
{
j=;
len=strlen(s);
for ( i= ; i<len ; i++ )
{
ss[j++]=s[i];
ss[j++]='#';//执行完语句j才会自增1
}
//ss[j]='^';
//printf("%s\n",ss);
result = judge(j);
printf("%d\n",result);
}
return ;
}
//下面这里是自己实现的代码，貌似不太行23333
/*int judge( int len )
{
len=(len+1)*2+1;//比ss多一个数字，是小于
int max=0, i=3 , count=1;
while ( i<len )
{
if ( ss[i]=='#' )
{
while ( 1 )
{
if ( (i-count*2+1)>=0 || (i+count*2-1)>=len ) break;
if ( ss[i-count*2+1] == ss[i+count*2-1] )
{
if ( count > max ) max=count;
count++;
}
else
{
count=1;
break;
}
}
}
else
{
while ( 1 )
{
if ( ss[i+count*2] == ss[i-count*2])
{
if ( count > max ) max=count;
count++;
}
else
{
count=1;
break;
}
if ( (i-count*2)>=0 || (i+count*2)>=len ) break;
}
}
i++;
}
return max;
}*/
吉哥系列故事——完美队形II
吉哥又想出了一个新的完美队形游戏！
假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] ... h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形：
假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] ... h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形：
1、挑出的人保持原队形的相对顺序不变，且必须都是在原队形中连续的；
2、左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然如果m是奇数，中间那个人可以任意；
3、从左到中间那个人，身高需保证不下降，如果用H表示新队形的高度，则H[1] <= H[2] <= H[3] .... <= H[mid]。
现在吉哥想知道：最多能选出多少人组成新的完美队形呢？
Input 输入数据第一行包含一个整数T，表示总共有T组测试数据(T <= 20)；
每组数据首先是一个整数n(1 <= n <= 100000)，表示原先队形的人数，接下来一行输入n个整数，表示原队形从左到右站的人的身高（50 <= h <= 250，不排除特别矮小和高大的）。Output 请输出能组成完美队形的最多人数，每组输出占一行。Sample Input
2
3
51 52 51
4
51 52 52 51
Sample Output
3
4
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
#define MAXN 100010*2
/*这题我知道是运用马拉车算法*/
/*在manacher算法上要加上对身高的判断，中间的人身高会比较高*/
/*检查BUG检查了好久好久= =，最后发现只要在那个地方加入一条判断就可以了= =*/
int a[MAXN], b[MAXN], p[MAXN]; int manacher(int len)
{
int mx=, id=, i, j;
for ( i= ; i<=len ; i++ )
{
if ( mx > i )
{
p[i]=min( p[*id-i] , mx-i );
}
else p[i]=;
while ( i+p[i] <= len && b[ i-p[i] ] == b[ i+p[i] ] && b[i-p[i]]<=b[i-p[i]+] )
{//加入的条件就是上面最后一个条件
/*if ( i%1 )
{
if ( b[i+1] < b[ i+1+p[i]*2 ] ) break;
}
else
{
if ( b[i] < b[ i+p[i]*2 ] ) break;
}*/
p[i]++;
}
if ( p[i]+i > mx )
{
mx=p[i]+i;
id=i;
}
}
int Max=;
for ( j= ; j<=len+ ; j++ )
{
if ( Max < p[j] ) Max=p[j];
}
return Max-;
} int main(void)
{
int repeat, i, n, temp, j;
scanf("%d", &repeat);
while ( repeat-- )
{
memset( b , , sizeof(b) );
scanf("%d" ,&n);
b[]=-;
for ( i=, j= ; i<n ; i++ )
{
scanf("%d", &a[i] );
b[j++]=a[i];
b[j++]=-;
}
b[j]=-;
/*for ( i=0 ; i<=j ; i++ )
{
printf("%d ", b[i] );
}*/
cout<<manacher(j)<<endl;
}
return ;
}