HDU 3068 最长回文

Description:

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input:

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output:

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input:

aaaa
abab

Sample Output:

4
3

题目链接

求最长回文子串,Manacher算法模板题。

推荐一篇Manacher算法博客,很详细。

马拉车(manacher) 算法

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

char ConvertStr[maxn << 1];
int Len[maxn << 1];

int Manacher(char Str[]) {
int L = 0, StrLen = int(strlen(Str));
ConvertStr[L++] = '$'; ConvertStr[L++] = '#';
for (int i = 0; i < StrLen; ++i) {
ConvertStr[L++] = Str[i];
ConvertStr[L++] = '#';
}
int MX = 0, ID = 0, Ans = 0;
for (int i = 0; i < L; ++i) {
Len[i] = MX > i ? min(Len[2 * ID - i], MX - i) : 1;
while (ConvertStr[i + Len[i]] == ConvertStr[i - Len[i]]) {
Len[i]++;
}
if (i + Len[i] > MX) {
MX = i + Len[i];
ID = i;
}
Ans = max(Ans, Len[i] - 1);
}
return Ans;
}

char Str[maxn];

int main(int argc, char *argv[]) {
while (~scanf("%s", Str)) {
printf("%d\n", Manacher(Str));
}
return 0;
}
文章目录
  1. 1. Description:
  2. 2. Input:
  3. 3. Output:
  4. 4. Sample Input:
  5. 5. Sample Output:
    1. 5.1. 题目链接
    2. 5.2. 马拉车(manacher) 算法
  6. 6. AC代码:
|