最長文字列アルゴリズム

総じて,最長文字列アルゴリズムは以下のように分類される.
暴力法
最も長い文字列の検索は、文字列全体を巡回することによって実現され、まず1つの文字列のすべてのサブ列、個数はn 2個であり、その後、巡回を1つずつ判断すればよい.アルゴリズム複雑度O(n 3)コードは以下の通りである.

def is_palindrome(s):
    str_length = len(s)

    for i in range(str_length / 2):
        if s[i] != s[str_length - 1 - i]:
            return False

    return True

#      
def algorithm1(s):
    length = len(s)

    for i in range(length):
        for j in range(i + 1):
            if is_palindrome(s[j: length - i + j]):
                return len(s[j: length - i + j])

    return 1

ダイナミックプランニング
センタ拡張法
このアルゴリズムはManacherアルゴリズムの前身と感じられるでしょう.文字の中心を使って両側に拡張することで、文字列を一度遍歴し、文字ごとに個別の判断を行うだけです.コードは次のとおりです.

def change(s):
    l = []
    for c in s:
        l.append(c)

    return "@#%s#" % "#".join(l)

#      
def algorithm3(s):
    s = change(s)
    flag = 0
    for i in range(2, len(s) - 2):
        temp = 1
        while s[i - temp] == s[i + temp]:
            temp += 1

        if temp > flag:
            flag = temp

    return flag - 1

実は中心解法は文字列を修正しなくてもいいのですが、それは処理が面倒で、コードを書くのに苦労します.
Manacherアルゴリズム
これは牛割りのアルゴリズムで、実は中心拡張法の最適化だと感じていますが、私は長い間やってやっと大体分かりました.主にその中にいくつかの難点があるからです.

文字列を変換する必要がある

補助配列の使用最適化計算は比較的理解しにくい

である.

アルゴリズム複雑度分析

この方法の牛割りは,そのアルゴリズムの複雑さがO(n)であり,暴力解法を考えるのは簡単であるが,直感的にはアルゴリズムの複雑さがあまりにも劣っていることにある.
文字列変換
ManacherにはP[i]p[i]というコア定義があるため、iを中心とした回文半径の長さはこの配列のため、文字列を変換する必要がある.なぜなら、P[i]という定義は、回文が奇数長文字列である場合にのみ存在するからである.
ほじょはいれつさいてきかけいさん
python実装のコードは次のとおりです.

def change(s):
    l = []
    for c in s:
        l.append(c)

    return "@#%s#" % "#".join(l)

# Manacher  
def algorithm4(s):
    s = change(s)
    p = [0] * len(s)
    index = 0
    for i in range(2, len(s) - 2):
        if p[index] + index > i:
            p[i] = min(p[2 * index - i], p[index] + index - i)
        else:
            p[i] = 1

        while s[i - p[i]] == s[i + p[i]]:
            p[i] += 1

        if index + p[index] < i + p[i]:
            index = i

    return max(p) - 1

中には、p[index]+index>iの代表的な意味はP配列の概念と結びつけて理解できるという判断があり、p[index]はindexを中心とした回文半径長であり、indexはそのインデックス値であるため、p[index]+indexの意味はindexを核心とする回文放射範囲if p[index]+index>i:次の遍歴点を説明し、indexを核心とするエコー放射範囲内では、放射範囲内である以上、pの開始計算位置は少なくともp[2*index-i]、またはp[index]+index-iから始まることを示す.ここは比較的回ります.ここで説明します

p[2*index-i]:2*index-iとiはindexに関して対称であるため、回文自体の特徴から、p[i]>=p[2*index-i]

p[index]+index-i:この値は実際に放射範囲からiを除去した.

両者の概念は似ていて、実は主に対称点を見ているので、対称点p[2*index-i]に基づいて、この値がp[index]の放射範囲を超えた場合、p[index]+index-iを取って、さもなくば値自体を取っています.どちらかというと回りくどいですが、実は自分で絵を描いてみると、これは分かりやすいです.
アルゴリズム複雑度分析
このアルゴリズムは私から見れば,以前の中心アルゴリズムよりも最適化されているが,なぜこのアルゴリズムの複雑さがO(n)なのか少しも見えず,後で多くの人の説明を見た.manacherアルゴリズムは、前処理された文字列を線形にスキャンするだけです.最適化後,pは解法中であり,文字列の各文字に対してスキャンは最大2回のみであり,時間複雑度は必然的にO(n)である.