Pythonで回文出力プログラム

回文とは

左から読んでも右から読んでも同じ文字列のこと。それに意味があるかどうかは今回の場合は問わない。
文字列$ p = p_1... p_n$について
$p_i = p_{n + 1 -i} (i\le 1 \le n) $
が成り立つものと定義する。
例えば、文字列'abcba'の回文は'abcba'、'bcb、'a'、'b'、'c'となる。

問題

入力されたテキストから回文となる文字列を全て出力する。

プログラム

findAllParindrome
入力： 文字列s、文字列の長さlen_s
出力: 回文を含む集合par

内部関数seek
入力： 文字列s, 着目位置index, 着目位置からの距離diff, 集合par
出力: なし

def findAllParindrome(s, len_s):
    par = set() # 集合のビルトインクラス
    new_str = "*|" # “*”は文字列の始端末端につけておく。 “|”は回文を奇数偶数関係なく判断するために文字同士間に挿入しておくe.g.) abc -> *|a|b|c|*
    for i in range(len_s ):
        tmp =  s[i] + "|" # “|”の挿入
        new_str += tmp 
    new_str += "*" # 末端識別子としてつけておく

    for i in range(2, 2 * len_s + 2): # 新たな文字列の記号以外の開始部分から終了部分まで

        seek(new_str, i, 0, par)# 探査をして回文を探査する

    return par

def seek(s, index, diff, par):
    """ check left letters and right letters iteratively """
    left = index - diff # 末端に到達した場合探査を終了
    right = index + diff
    if s[left] == "*" or s[right] == "*":
        return
    # print(s[left], s[right], end="")
    if s[left] != s[right]: # 左右が一致しない場合探査を終了
        return 
    else: # 左右が一致した場合 
        seek(s, index, diff + 1, par)# 次の左右の文字列探索をする
        if s[index + diff] != "|":  # 参照している右の文字列が”|”でない時
            tmp = s[index - diff: index + diff + 1: 2]  # “|”を飛ばして文字列をtmpに代入
            print(s[index - diff: index + diff + 1: 2], end=" ")
            par.add(tmp)

def test_par():
    assert findAllParindrome("たけやぶやけた", 7) == {'け', 'けやぶやけ', 'た', 'たけやぶやけた', 'ぶ', 'や', 'やぶや'}
    assert findAllParindrome("abcba", 5) == {'a', 'abcba', 'b', 'bcb', 'c'}

プログラムのポイント

• 1文字の回文や文字列の奇数偶数の場合の処理をまとめるために、文字列間に"|"と末端文字"*"を入れてみた
• 線形探索で文字列を左から右へ読み込む
• 左右の文字列が一致したら一つ先の左右の文字列へ再帰的に進めていく

処理時間

a-zまでの小文字のランダムの繰り返し文字列を入力して処理した場合

abab...の繰り返し文字列を入力した場合

繰り返し文字列"ab"を入力文字列としてログラムを実行した時の処理時間。abという文字列を繰り返すことでseek関数の処理数が増加するので、処理時間が指数関数的に増加すると考えられる。