最长回文

                                                               Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768
K (Java/Others)

                                                                                                  Total Submission(s): 11760    Accepted Submission(s): 4308

                                                                                 链接：Click Me！

aaaa

abab

4

3

分析：

求解最长回文串，曾经我是用DP来做的，在这个题目里面，O(N^2)的复杂度肯定是会超时的，于是我今天第一回敲了个Manacher的模板，挺方便的，复杂度也降了一个数量级，复杂度仅仅有O（N）。Orz...

实现代码：

#include <map>

#include <cmath>

#include <queue>

#include <vector>

#include <cstdio>

#include <string>

#include <cstring>

#include <sstream>

#include <iostream>

#include <algorithm>

using namespace std;

#define FIN             freopen("input.txt","r",stdin)

#define FOUT            freopen("output.txt","w",stdout)

#define CASE(T)         int T;for(scanf("%d",&T);T--;)

const int maxn = 110000 + 5;

char Ma[maxn << 1];

int Mp[maxn << 1];

void Manacher(char s[], int len)

{

    int l = 0;

    Ma[l++] = '$';

    Ma[l++] = '#';

    for(int i = 0; i < len; i++)

    {

        Ma[l++] = s[i];

        Ma[l++] = '#';

    }

    Ma[l] = 0;

    int mx = 0, id = 0;

    for(int i = 0; i < l; i++)

    {

        Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;

        while(Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;

        if(i + Mp[i] > mx)

        {

            mx = i + Mp[i];

            id = i;

        }

    }

}

char s[maxn];

int main()

{

#ifndef ONLINE_JUDGE

    FIN;

#endif // ONLINE_JUDGE

    while(~scanf("%s", s))

    {

        int len = strlen(s);

        Manacher(s, len);

        int ans = 0;

        for(int i = 0; i < 2 * len + 2; i++)

        {

            ans = max(ans, Mp[i] - 1);

        }

        printf("%d\n", ans);

    }

    return 0;

}