POJ 3974 Palindrome Manacher

#include<iostream>
#include<string>
using namespace std;

string s;
int cnt = 0;

int min(int a, int b){ return a>b ? b : a; }
int max(int a, int b){ return a>b ? a : b; }

int Manacher()
{
    int len = s.length();
    if(len == 0) return 0;
    len = 2*len+1;
    char *cArr = new char[len];
    int *pArr = new int[len];
    for(int i = 0; i < len; i++)
        cArr[i] = i&1 ? s[(i-1)/2] : ‘#‘;
    
    int R = -1;
    int C = -1;
    int maxn = 0;
    for(int i = 0; i < len; i++)
    {
        pArr[i] = i >= R ? 1 : min(R-i, pArr[2*C-i]);
        while(i+pArr[i] < len && i-pArr[i] > -1)
            if(cArr[i+pArr[i]] == cArr[i-pArr[i]]) pArr[i]++;
            else break;
        if(i+pArr[i] > R)
        {
            R = i + pArr[i];
            C = i;
        }
        maxn = max(maxn, pArr[i]);
    }
    delete[] pArr;
    delete[] cArr;
    return maxn-1;
}

int main()
{
    while(getline(cin, s))
    {
        if(s == "END") break;
        printf("Case %d: %d\n", ++cnt, Manacher());
    }
    //system("pause");
    return 0;
}

POJ 3974 Palindrome Manacher

原文：https://www.cnblogs.com/znk97/p/14030023.html