回文自动机 学习笔记
Manacher解决的问题:O(n)时间内求出字符串以每个点为中心时的最长回文长度
1.对字符串的预处理
一般为了避免无限制的匹配下去,会在开头和结尾加入未在原字符串中出现的‘#’
一般为了方便判断,一般在原字符串的字符之间加入未在原字符串中出现的‘#’,
新串由两部分组成,新加入的‘#’字符的个数就是len[原串]+1,原字符串为len[原串],所以
这样新串的所有回文串的长度都变成了奇数,并且原回文的长度为(新串回文半径 - 1)
2.定义len[]
这里定义len[i]代表新串中的回文半径,len[i]-1就代表了原串中的回文长度,这样问题就转化为了求len[]
3.如何在线性时间内求解len[]
对len[]的计算按照从左往右一次进行,在计算len[i]时,len[j](j∈[0,i-1])都是已知的。
这里维护一个MaxR,代表j+len[j]-1(j∈[0,i-1])的最大值,即在[0,i-1]计算过程中右端点的最大值
同时维护取得最大值的位置,记为P。MaxR关于P的对称点记为MaxR`,i关于P的对称点记为j。
可能出现的情况有三种:
① i <= MaxR && len[j] + i - 1 < MaxR
由对称性可知len[i] = len[j]
② i <= MaxR && len[j] + i - 1 >= MaxR
此时以i为中心的回文串可能会延伸到MaxR的右边,所以要从P开始匹配,匹配完成后更新变量
③ i > MaxR
此时无法利用P的回文串,直接对于以i为中心的串暴力匹配,匹配完成后更新变量
4.例题POJ-3974
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 10;
char s1[maxn], s2[maxn * 2 + 10];//s1原串,s2新串
int l, len[maxn * 2 + 10];
void init()
{
l = 0;
int n = strlen(s1);
s2[++l] = '#';
s2[++l] = '#';
for (int i = 0; i < n; i++)
{
s2[++l] = s1[i];
s2[++l] = '#';
}
s2[l + 1] = '\0'; // 结束字符
}
inline void manacher()
{
int MaxR = 0, P = 0; // 定义MaxR与P
for (int i = 1; i <= l; i++)
{
int now_len;//当前位置的len
if (MaxR < i) now_len = 1; //如果是第③种情况
else now_len = min(len[P * 2 - i], MaxR - i); //第①②种情况
// 逐位匹配在第①种情况下是不会进行的,仅在②③种情况下进行,由对称性决定
while (s2[i + now_len] == s2[i - now_len]) ++now_len;
// 更新最右点
if (i + now_len > MaxR)
{
MaxR = i + now_len;
P = i;
}
len[i] = now_len;
}
}
int main() {
int T = 0;
while (scanf("%s", s1), memcmp(s1, "END", 4) != 0)
{
init();
manacher();
int ans = 0;
for (int i = 1; i <= l; i++) ans = max(ans, len[i] - 1);
printf("Case %d: %d\n", ++T, ans);
}
return 0;
}
上一篇: 盘点2017最精辟最火的句子