# HDU3036 最长回文（最长回文子串）

## 最长回文

• Time Limit: 4000/2000 MS (Java/Others)
• Memory Limit: 32768/32768 K (Java/Others)
• Total Submission(s): 27578
• Accepted Submission(s): 10050

aaaa
abab

4
3

### Source

2009 Multi-University Training Contest 16 - Host by NIT

lcy

### 链接

http://acm.hdu.edu.cn/showproblem.php?pid=3068

### 题解

manacher（马拉车）算法，时间复杂度O(n)。

### 代码

StatusAccepted
Time390ms
Memory2840kB
Length995
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110010;
char s[maxn];
char ss[maxn*2];
int p[maxn*2];

int init()
{
ss[0] = '\$';
ss[1] = '#';
int l = strlen(s), k = 2;
for (int i = 0; i < l; ++i) // 对原串进行变形
{
ss[k++] = s[i];
ss[k++] = '#';
}
ss[k] = '\0';
return k;
}

int manacher()
{
int l = init();
int id, mx = 0, ans = 0;
for (int i = 1; i < l; ++i)
{
if (i < mx) // 在mx覆盖范围之内
p[i] = min(mx - i, p[2 * id - i]);
else // 单独一点
p[i] = 1;
while (ss[i - p[i]] == ss[i + p[i]]) // 左右扩张
p[i]++;
if (mx < i + p[i]) // 更新
{
id = i;
mx = i + p[i];
}
ans = max(ans, p[i] - 1); // 答案更新
}
return ans;
}

int main()
{
while (scanf("%s", s) != EOF)
{
memset(p, 0, sizeof(p));
printf("%d\n", manacher());
}
return 0;
}

The end.
2018-05-25 星期五