Manacher(处理最长回文的类似问题)_综合

1. 将字符串中的数变为奇数
2. p[i]表示最长回文长度左右扩张的长度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 110005;
char target[maxn];
char target01[maxn<<1];
int p[maxn<<1];void Manacher(char target01[])   //p[i]中最大的减一就为最长回文子串
{//计算p[i]int i, id = 0, mx = 0;p[0] = 0;for(i = 1; target01[i]; ++i){if(mx > i) p[i] = min(p[2*id - i], mx - i);else p[i] = 1;while(target01[i+p[i]] == target01[i-p[i]])p[i]++;if(mx < p[i] + i){mx = p[i] + i;id = i;}}
}
void init()   //处理字符串
{int j = 2;target01[0] = '$';target01[1] = '#';for(int i = 0; target[i]; ++i){target01[j++] = target[i];target01[j++] = '#';}target01[j] = '\0';
}