manacharアルゴリズム学習ノート

manacharアルゴリズムは文字列の最長回文子列を処理するアルゴリズムであり、その核心は前処理len配列である.
元の列がs[0...n-1]であると仮定し、len[i]はs[i]を回文の中心とする最長の回文列の右下からiまでの長さを表す.
そしてでたらめを繰り返す.
アルゴリズム自体が簡単なネット上の腐った街なので、主に複雑さを考えた.
Maxポインタは最大nまで拡張されることが容易にわかりますが、複雑さは主にwhileサイクルにあり、毎回Maxポインタが増加します.
針や飛び出しwhileサイクルのため、複雑度はO(n+chang(Max)=O(n)が最も多い.
HDU 3068:クリックしてリンクを開く
テンプレート問題

#include <bits/stdc++.h>
using namespace std;
#define maxn 111111

int len[maxn<<1];
char a[maxn];

int manachar (char *p) {
    char s[maxn<<1];//    
    int n = strlen (p), l = 0;
    s[l++] = '@';
    s[l++] = '#';
    for (int i = 0; i < n; i++) {
        s[l++] = p[i];
        s[l++] = '#';
    }
    s[l++] = '~'; s[l] = 0;
    //cout << s << endl;

    int Max = 0, pos = 0, ans = 0;
    for (int i = 1; i < l; i++) {
        if (Max > i) {
            len[i] = min (len[2*pos-i], Max-i);
        }
        else
            len[i] = 1;
        while (s[i+len[i]] == s[i-len[i]])
            len[i]++;
        ans = max (ans, len[i]);
        if (len[i]+i > Max) {
            Max = len[i]+i;
            pos = i;
        }
    }
    return ans-1;
}

int main () {
    while (scanf ("%s", a) == 1) printf ("%d
", manachar (a));
    return 0;
}

POJ 3974:クリックしてリンクを開く

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 2211111

int len[maxn];
char s[maxn];
char a[maxn];

int Manachar (char *p) {
    int n = strlen (p), l = 0;
    s[l++] = '@';
    s[l++] = '#';
    for (int i = 0; i < n; i++) {
        s[l++] = p[i];
        s[l++] = '#';
    }
    s[l] = 0;

    int Max = 0, pos = 0, ans = 0;
    for (int i = 1; i < l; i++) {
        if (Max > i) {
            len[i] = min (len[2*pos-i], Max-i);
        }
        else
            len[i] = 1;
        while (s[i+len[i]] == s[i-len[i]])
            len[i]++;
        ans = max (ans, len[i]);
        if (len[i]+i > Max) {
            Max = len[i]+i;
            pos = i;
        }
    }
    return ans-1;
}

int main () {
    int kase = 0;
    while (scanf ("%s", a) == 1) {
        if (a[0] == 'E')
            break;
        printf ("Case %d: %d
", ++kase, Manachar (a));
    }
    return 0;
}