(Manacher) 算法
(1.) 算法概述
给定字符串 (s)，可以在 (O(n)) 时间内处理出以每个位置 (i) 为回文中心所具有的回文串的长度，进而可以在 (O(n)) 时间内求出 (s) 的最大回文子串长度
(2.) 算法详解
(2.1) 引入参数
设 (s = abcba) 如下
|(0)|(1)|(2)|(3)|(4)|(5)|(6)|
|-|-|-|-|-|-|-|-|-|-|-|
||(a)|(b)|(c)|(b)|(a)|(ackslash 0)|
(2.1.1) (str) 字符串
(str) 表示 (s) 处理后的串
为了避免对回文串长度奇偶性的讨论
考虑在 (s) 的首尾、以及中间每两个字符中插入分隔符 ($)
并且在 (str) 首部位置插入一个哨兵 ($)
(str) 具体的构造如下
|(0)|(1)|(2)|(3)|(4)|(5)|(6)|(7)|(8)|(9)|(10)|(11)|(12)|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|($)|($)|(a)|($)|(b)|($)|(c)|($)|(b)|($)|(a)|$|(ackslash 0)|
对应的代码如下
int L = strlen(s + 1);
for(int i = 1; i <= L; ++i)
str[2 * i] = s[i], str[2 * i + 1] = '$';
L = L * 2 + 1, str[0] = str[1] = '$', str[L + 1] = ' ';
(2.1.2) (pleft[i ight]) 数组
(p[i]) 表示每个位置 (i) 可以扩展的最大长度，也等于以位置 (i) 为回文中心的回文串长度
构造如下
|(0)|(1)|(2)|(3)|(4)|(5)|(6)|(7)|(8)|(9)|(10)|(11)|(12)|
|-|-|-|-|-|-|-|-|-|-|-|-|-|-|
|($)|($)|(a)|($)|(b)|($)|(c)|($)|(b)|($)|(a)|($)|(ackslash 0)|
||(0)|(1)|(0)|(1)|(0)|(5)|(0)|(1)|(0)|(1)|(0)||
(2.1.3 mid, maxr)
(maxr) 表示当前所有回文子串中的最右端点，(mid) 表示这个回文子串的回文中心
(2.2) 构造 (p[i])
(manacher) 算法复杂度之所以优秀，关键在于 (p[i]) 的构造
基本的思想在于利用已知的 (maxr, mid) 来计算 (p[i])，具体可以分成两类
(2.2.1) (i < maxr)
图源洛谷，(pos) 即 (mid)，示例如下
设 (j) 是 (i) 关于 (mid) 的对称点
由对称性可知，填色的两个回文串一模一样，所以 (p[i] = p[j])
但若回文长度过长，超出了 (maxl/ maxr)，如下所示
那么 (p[i] = j - maxl = maxr - i)
所以取二者最小即可
(2.2.2) (igeq maxr)
只能暴力拓展
具体代码如下
for(int i = 1; i <= L; ++i) {
if(i < maxr) p[i] = min(p[2 * mid - i], maxr - i);
while(str[i - p[i] - 1] == str[i + p[i] + 1]) ++p[i]; //暴力拓展
if(i + p[i] > maxr) maxr = i + p[i], mid = i; //更新 maxr, mid
}
(2.3) 算法复杂度分析
每次暴力拓展时，更新 (maxr)
而 (maxr) 一直在右移，移动次数总计 (O(n)) 次
加上一个遍历的复杂度 (O(n))
故总的复杂度仍然为 (O(n))
(3.) 代码模板
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL MOD = 11092019;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int N = 4e7 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
char s[N], str[N];
int L, p[N];
void manacher()
{
for(int i = 1; i <= L; ++i) str[2 * i] = s[i], str[2 * i + 1] = '$';
L = L * 2 + 1, str[0] = str[1] = '$', str[L + 1] = ' ';
int mid = 0, maxr = 0;
for(int i = 1; i <= L; ++i) {
if(i < maxr) p[i] = min(p[2 * mid - i], maxr - i);
while(str[i - p[i] - 1] == str[i + p[i] + 1]) ++p[i];
if(i + p[i] > maxr) maxr = i + p[i], mid = i;
}
}
int main()
{
scanf("%s", s + 1);
L = strlen(s + 1);
manacher();
int ans = 0;
for(int i = 1; i <= L; ++i) ans = max(ans, p[i]);
cout<<ans<<endl;
return 0;
}
(4.) 应用
(4.1) 求最长回文前缀
用 (manacher) 预处理 (p[i]) 数组
对于新字符串 (str) 的每一个位置 (i)，判断其回文半径是否触及左端点 (1)，即 (i - p[i] = 1)，若可以触及，说明是一个回文前缀，更新长度即可
代码如下
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define arrayDebug(a, l, r) for(int i = l; i <= r; ++i) printf("%d%c", a[i], "
"[i == r])
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL MOD = 11092019;
const int inf = 0x3f3f3f3f;
const int DX[] = {0, -1, 0, 1, 0, -1, -1, 1, 1};
const int DY[] = {0, 0, 1, 0, -1, -1, 1, 1, -1};
const int N = 4e7 + 7;
const double PI = acos(-1);
const double EPS = 1e-6;
using namespace std;
inline int read()
{
char c = getchar();
int ans = 0, f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {ans = ans * 10 + c - '0'; c = getchar();}
return ans * f;
}
char s[N], str[N];
int L, p[N];
void manacher()
{
for(int i = 1; i <= L; ++i) str[2 * i] = s[i], str[2 * i + 1] = '$';
L = L * 2 + 1, str[0] = str[1] = '$', str[L + 1] = ' ';
int mid = 0, maxr = 0;
for(int i = 1; i <= L; ++i) {
if(i < maxr) p[i] = min(p[2 * mid - i], maxr - i);
while(str[i - p[i] - 1] == str[i + p[i] + 1]) ++p[i];
if(i + p[i] > maxr) maxr = i + p[i], mid = i;
}
}
int main()
{
scanf("%s", s + 1);
L = strlen(s + 1);
manacher();
int ans = 0;
for(int i = 1; i <= L; ++i)
if(i - p[i] == 1) ans = max(ans, p[i]);
cout<<ans<<endl;
return 0;
}