マラカーアルゴリズムManacher+例題:hihocoder〓1032最長回文子列

2376 ワード
板
【マラ車Manacherアルゴリズム】
インポート:
文字列の一番長い回文列を計算する最もシンプルなアルゴリズムは列挙文字列の各部分列であり、この部分列が回文列かどうかを判断します.このアルゴリズムの複雑度はO(n^3)で、明らかに満足できません.少し最適化したアルゴリズムはエニュメレート・回文列の中点であり、ここでは二つの場合に分けられます.一つは文字列の長さが奇数の場合、もう一つは文字列の長さが偶数の場合です.エニュメレート・中点は回文列かどうかを判断し、アルゴリズムの時間複雑度をO(n^2)に下げることができますが、nが大きいと満足できません.Manacherアルゴリズムは、O(n)時間の複雑さの中で、最も長い文字列の文字列を求めて、理論的な下界に到達します.
実装:
Manacherアルゴリズムは中心拡散法に基づいて、空間的に時間を変える考え方を採用して、最長回文子列の複雑さをO(n)に下げる巧みな方法です.
考え方:奇数の文字列の長さと偶数の文字列を一緒に考えるために、元の文字列の各隣の2つの文字の間に1つの区切り記号を挿入します.同時に最初の尾にも1つの区切り記号を追加します.区切り記号の要求は元の列には現れません.一つの配列Len[i]で文字S[i]を中心とした一番長い文字列の一番右文字からS[i]までの長さを表し、例えばS[i]を中心とした一番長い文字列はS[l,r]であり、Len[i]=r-i＋1である.Len配列は、リーン[i]-1が元の文字列Sの長さであるという性質を持っている.
Len配列の計算:
rightを文字S[i]を中心とした一番長い文字列の一番右文字の位置とし、posを文字S[i]の位置i,iを左から右にマッチングさせる.
二つの場合があります.①i②i>=rightの場合は、T[i]を中心とした回文列が一つもマッチしていないことを説明しますので、Len[i]=1は、最初から一つずつ下に合わせる必要があります.
時間複雑度O(n),空間複雑度O(n).
【タイトル】
最長回文子文字列
【コード】
#include 
using namespace std;
const int maxn = 1e6 + 10;
char s[maxn];
char t[maxn<<1];
int Len[maxn<<1];
int len;
void init()
{
    int k=0;
    t[k++]='#';
    for(int i = 0; i < len; i++){
        t[k++] = s[i];
        t[k++] = '#';
    }
    len = k;
}

int Manacher()
{
    int sum = 0, right = 0, pos = 0;
    for(int i = 1; i < len; i++){
        if(i < right){
            Len[i] = min(right - i, Len[2 * pos - i]);
        }
        else{
            Len[i]=1;
        }
        while(t[i - Len[i]] == t[i + Len[i]]){
            Len[i]++;
        }
        if(Len[i] + i > right){
            right = Len[i] + i;
            pos = i;
            sum = max(sum, Len[i]);
        }
    }
    return sum - 1;
}
int main()
{
    int n; scanf("%d", &n);
    while(n--){
        scanf("%s", s);
        len = strlen(s);
        init();
        int ans = Manacher();
        printf("%d
", ans);
    }
    return 0;
}
【自考】データ構造試験前まとめ【CH 1-CH 3】
デザインモードの策略パターン学習