【Python】部分文字列が別の文字列と完全一致、または1文字だけ異なる開始インデックスを見つけるプログラム

問題の概要

2つの文字列が与えられたとします。1つ目の文字列は2つ目よりも長く、1つ目の文字列から切り出した部分文字列が、2つ目の文字列と完全に一致する、もしくはちょうど1文字だけ異なるかどうかを調べます。そして、条件を満たす部分文字列が始まる位置(インデックス)をすべて返すのが目的です。

たとえば、入力が string1 = 'tpoint'、string2 = 'pi' の場合、出力は「1 2」になります。

これは、1つ目の文字列のインデックス1と2から始まる長さ2の部分文字列「po」「oi」が、それぞれ「pi」と比べてちょうど1文字だけ異なっているためです。

解法の考え方:Zアルゴリズム

この問題はZアルゴリズムを使うと効率的に解けます。Zアルゴリズムとは、文字列の各位置について「その位置から始まる部分文字列が、文字列の先頭と何文字一致するか」を前処理で一括計算できる手法です。素朴にすべての位置を総当たりで比較する方法(O(n・m))に比べ、線形時間 O(n + m) で処理できる点が大きなメリットです。

手順

• search() 関数を定義する(string1 と string2 を引数に取る)。この関数は、連結文字列 string1 + string2 に対してZ配列を構築します。
  • str_cat := string1 + string2
  • z_list := str_cat と同じ長さの、0で初期化された新しいリスト
  • z_list[0] := str_cat の長さ
  • right := 0、left := 0
  • i を 1 から str_cat の長さまでループ:
    • i > right の場合:
      • j := 0 とし、j + i が str_cat の長さ未満 かつ str_cat[j] == str_cat[j+i] の間、j を増やし続ける
      • z_list[i] := j
      • j > 0 ならば、left := i、right := i + j − 1
    • それ以外の場合:
      • k := i − left、r_len := right − i + 1
      • z_list[k] < r_len ならば z_list[i] := z_list[k](すでに計算済みの情報を再利用)
      • そうでなければ、m := right + 1 から一致を延長し、z_list[i] := m − i、left := i、right := m − 1
    • z_list[i] := min(len(string1), z_list[i])
  • z_list[len(string1):](string1 の長さ以降のスライス)を返す
• fwd := search(str2, str1)(各位置における順方向の一致長)
• bwrd := search(str2[::-1], str1[::-1]) を計算し、結果のリストを反転する(逆方向の一致長)
• idx := 新しい空リスト
• i を 0 から len(str1) − len(str2) までループ:
  • fwd[i] + bwrd[i + len(str2) − 1] ≥ len(str2) − 1 ならば、i を文字列として idx の末尾に追加
• idx が空なら False を返す。そうでなければ、idx の要素を空白区切りで連結した文字列を返す

判定条件のポイント

注目しているウィンドウ(比較対象の部分文字列)について、先頭側から何文字一致しているか(fwd)と末尾側から何文字一致しているか(bwrd)の合計が「len(str2) − 1」以上であれば、不一致は最大でも1文字しか存在しないことになります。これが条件式の正体です。順方向と逆方向のZ配列を組み合わせることで、各ウィンドウの判定を定数時間で行えるようになります。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def search(string1, string2):
    str_cat = string1 + string2
    z_list = [0] * len(str_cat)
    z_list[0] = len(str_cat)
    right = 0
    left = 0
    for i in range(1, len(str_cat)):
        if i > right:
            j = 0
            while j + i < len(str_cat) and str_cat[j] == str_cat[j+i]:
                j += 1
            z_list[i] = j
            if j > 0:
                left = i
                right = i + j - 1
        else:
            k = i - left
            r_len = right - i + 1
            if z_list[k] < r_len:
                z_list[i] = z_list[k]
            else:
                m = right + 1
                while m < len(str_cat) and str_cat[m] == str_cat[m -i]:
                    m += 1
                z_list[i] = m - i
                left = i
                right = m - 1
        z_list[i] = min(len(string1), z_list[i])
    return z_list[len(string1):]

def solve(str1, str2):
   fwd = search(str2, str1)
   bwrd = search(str2[::-1], str1[::-1])
   bwrd.reverse()
   idx = []
   for i in range(len(str1) - len(str2)+1):
      if fwd[i] + bwrd[i+len(str2)-1] >= len(str2)-1:
         idx.append(str(i))
   if len(idx) == 0:
      return False
   else:
      return (\" \".join(idx))

print(solve('tpoint', 'pi'))

入力

'tpoint', 'pi'

出力

1 2

まとめ

本記事では、Zアルゴリズムによる順方向・逆方向の一致長計算を組み合わせることで、「完全一致または1文字違い」の部分文字列を線形時間で検索する方法を紹介しました。テキスト長 n、パターン長 m に対して計算量は O(n + m) となり、大規模な文字列検索にも実用的なアプローチです。