競プロ超初心者が解く、回分最大長さの取得

概要

競技プログラミングの超初心者が、初心者向けの問題を解きます。
問題を回答するにあたって、使用する言語はPythonです。
問題を解いていている時の思考と、最適なアルゴリズムを調べて記事にしています。

回答した問題

文字列の中から回分となる箇所を探し出して、回分となる最大文字列を出力する問題です。
トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320) B - Kibgest Palindrome

自力の回答

提出コード

二重ループで文字列の左側開始位置と、終了位置を調整して部分的な文字列を網羅的に取得しています。文字列と逆の文字列を比較して、同等の文字列であれば現在の最大値を更新します。

s = input()
s_len = len(s)
max_len = 0

for i in range(s_len):
    for j in range(i+1, s_len+1):
        s_mid = s[i:j]
        if s_mid == s_mid[::-1]:
            max_len = max(max_len, len(s_mid))

print(max_len)

最適解

回答の問題点を確認

BingAIにコードを評価してもらいました。

競技プログラミングの回答で、次のプログラムを提出して合格しました。
提出したコードを評価して、問題点を箇条書きで出力してください。

---
{code}
---

二重ループだと、文字数が長い場合はプログラムの実行時間が長くなってしまうと指摘されました。他にも指摘された点はありましたが、適切ではなかったので省略しました。

コードの効率性が低いです。二重ループで全ての部分文字列を調べると、時間計算量がO(n^2)になります。
動的計画法やマンチェスター法などを使うと、時間計算量をO(n)に減らすことができます。

最適化されたコード

最適なアルゴリズムに書き換えたプログラムをBingAIに出力してもらい、確認していきます。Manacherというアルゴリズムを使用しているらしく、理屈は分かりませんが正しい答えが出力されました。

def manacher(s: str):
    # 文字間に#を挿入して奇数長にする
    t = "#" + "#".join(s) + "#"
    n = len(t)
    # 各位置での最長回文半径
    p = [0] * n
    # 現在注目している中心位置
    c = 0
    # 現在注目している中心位置からの最右端
    r = 0
    # 最長回文の長さ
    max_len = 0
    for i in range(n):
        # iがrより左にある場合は、対称位置の値を利用できる
        if i < r:
            p[i] = min(p[2 * c - i], r - i)
        # iがrより右にある場合は、1から始める
        else:
            p[i] = 1
        # 中心をiとして回文を拡張する
        while i - p[i] >= 0 and i + p[i] < n and t[i - p[i]] == t[i + p[i]]:
            p[i] += 1
        # 最右端と中心位置を更新する
        if i + p[i] > r:
            r = i + p[i]
            c = i
        # 最長回文の長さを更新する
        max_len = max(max_len, p[i] - 1)
    return max_len

s = input()
print(manacher(s))

さいごに

今の実力では、アルゴリズムについて学習する段階ではないため記事はここで終了します。
行き詰まった時に、アルゴリズムに関する記事を書いていこうかなと。