hihocode #1032 : 最长回文子串【manacher】模板题

题目链接:https://vjudge.net/problem/HihoCoder-1032

manacher算法详解:https://blog.csdn.net/dyx404514/article/details/42061017

题目大意:

给出一段字符串,输出其中最长回文字串的长度。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = ;
char str[maxn];//原字符串
char tmp[maxn << ];//转换后的字符串
int Len[maxn << ]; //转换原始串
int init(char *st)
{
int i, len = strlen(st);
tmp[] = '@';//字符串开头增加一个特殊字符,防止越界
for (i = ; i <= * len; i += )
{
tmp[i] = '#';
tmp[i + ] = st[i / ];
}
tmp[ * len + ] = '#';
tmp[ * len + ] = '$';//字符串结尾加一个字符,防止越界
tmp[ * len + ] = ;
return * len + ;//返回转换字符串的长度
}
//Manacher算法计算过程
int manacher(char *st, int len)
{
int mx = , ans = , po = ;//mx即为当前计算回文串最右边字符的最大值
for (int i = ; i <= len; i++)
{
if (mx>i)
Len[i] = min(mx - i, Len[ * po - i]);//在Len[j]和mx-i中取个小
else
Len[i] = ;//如果i>=mx,要从头开始匹配
while (st[i - Len[i]] == st[i + Len[i]])
Len[i]++;
if (Len[i] + i>mx)//若新计算的回文串右端点位置大于mx,要更新po和mx的值
{
mx = Len[i] + i;
po = i;
}
ans = max(ans, Len[i]);
}
return ans - ;//返回Len[i]中的最大值-1即为原串的最长回文子串额长度
} int main()
{
int t; cin >> t;
while (t--)
{
scanf("%s", &str);
int len = init(str);
int ans = manacher(tmp, len);
printf("%d\n", ans);
}
return ;
}

2018-06-04

上一篇:细说JDK日志组件


下一篇:hihoCoder #1032 : 最长回文子串 [ Manacher算法--O(n)回文子串算法 ]