PythonでS1の接頭辞とS2の接尾辞を連結すると回文になるインデックスiを見つける方法

問題概要

同じ長さを持つ2つの文字列S1とS2が与えられたとき、S1[0…i]とS2[i+1…n-1]を連結した結果が回文になるようなインデックスiを見つけます。そのようなインデックスが存在しない場合は、-1を返します。

例えば、入力がS1 = "pqrsu"、S2 = "wxyqp"である場合を考えてみましょう。このとき出力は1になります。なぜなら、S1[0..1] = "pq"、S2[2..n-1] = "ypq"であり、これらを連結した"pqyqp"は回文になるためです。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• nにstr1のサイズ（長さ）を代入します

• 空文字列strを用意します

• iを0からnまで繰り返します

  • strにstr1[i]を連結します

  • 空文字列tempを用意します

  • jをi+1からnまで繰り返し、tempにstr2[j]を順次連結します

  • isPalindrome(str + temp)が真であれば、現在のiを返します

• すべての候補を確認しても回文が見つからない場合は、-1を返します

実装例

以下のPythonコードを実装することで、より深く理解できます。

def isPalindrome(s):
    if s == s[::-1]:
        return True
    return False

def find_index(str1, str2):
    n = len(str1)
    str = ""
    for i in range(n):
        str = str + str1[i]
        temp = ""
        for j in range(i + 1, n):
            temp += str2[j]
        if (isPalindrome(str + temp)):
            return i
    return -1

str1 = "pqrsu"
str2 = "wxyqp"
print(find_index(str1, str2))

入力

"pqrsu", "wxyqp"

出力

1

処理の流れのポイント

このアルゴリズムでは、外側のループでS1の接頭辞の長さを1文字ずつ増やしながら確認し、内側のループで対応するS2の接尾辞を組み立てています。回文判定にはスライス記法s[::-1]を使い、元の文字列と反転した文字列を比較するシンプルな方法を採用しています。

なお、この実装は二重ループの中で毎回文字列を組み立てているため、計算量はO(n³)程度になります。文字列が短い場合は問題ありませんが、より大きな入力に対しては、ローリングハッシュやKMPの失敗関数などを活用した最適化も検討するとよいでしょう。