HDU - 3068 最长回文

Posted on | In , ,

思路：
一道神奇的回文题，使用O(n^2)复杂度的算法会超时，需要使用manacher算法。manacher算法简而言之就是利用了已经获得的回文字符串左右对称的性质，观察现在所在的字符是不是在已有回文串中，利用回文串左边求得的回文长度来初始化右边来减少重复计算，需要记录当前会问能达到的最右端。复杂度为O(n)，因为最右端最多移动n次，所以复杂度很低。

代码：

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
39
40
41
42
43
44
45
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <cctype>
#include <sstream>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1+1)

using namespace std;
const int MAX = 110000 + 10;
int p[MAX*2];
int manacher(char *str){
    int pos = 0, r = 0,length=strlen(str),maxs = 0;;
    for (int i = 1;i < length;i++) {
    if (i < r)p[i] = min(r - i, p[2 * pos - i]); else p[i] = 1; while (str[i - p[i]] == str[i + p[i]])p[i]++; if (i + p[i]> r)r = i + p[i], pos = i;
        maxs = max(maxs, p[i]);
    }
    return maxs-1;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    char str[MAX*2],astr[MAX*2];
    while (cin >> str) {
        astr[0] = '$',astr[1]='#';
        int j = 2;
        for (int i = 0;str[i]!='\0';i++, j += 2)astr[j] = str[i], astr[j + 1] = '#';
        astr[j] = '\0';
        cout<<manacher(astr)<<"\n";
    }
    return 0;
}