PythonのSequenceMatcherで最長共通部分文字列を求める方法

はじめに

2つの文字列が与えられたとき、その中から最も長い共通部分文字列（Longest Common Substring）を見つけて出力するのが本記事の目的です。Pythonでは、標準ライブラリ difflib に含まれる SequenceMatcher クラスの find_longest_match() メソッドを使うことで、この問題を簡単かつ効率的に解決できます。

SequenceMatcherとは

difflib.SequenceMatcher は、要素がハッシュ可能である限り、任意の型のシーケンス同士を比較できる柔軟なクラスです。文字列だけでなく、リストやタプルなどの比較にも利用できます。

主に使用するメソッドは以下の通りです。

find_longest_match(alo, ahi, blo, bhi)

1つ目のシーケンスの a[alo:ahi] と、2つ目のシーケンスの b[blo:bhi] の範囲内で、最も長く一致するブロックを検索します。戻り値はMatchオブジェクトで、match.a は1つ目の文字列側の開始位置、match.b は2つ目の文字列側の開始位置、match.size は一致した部分の長さを表します。

実行例

Input:  str1 = "pythonprogramming",
        str2 = "pro"
Output: pro

アルゴリズム

Step 1: 2つの文字列を入力する。
Step 2: 入力された文字列でSequenceMatcherオブジェクトを初期化する。
Step 3: find_longest_match()で最長の一致部分を検索する。
Step 4: 最長の共通部分文字列を出力する。

サンプルコード

# Python program to find Longest Common Sub-string 
from difflib import SequenceMatcher 
def matchsubstring(m,n): 
   seqMatch = SequenceMatcher(None,m,n) 
   match = seqMatch.find_longest_match(0, len(m), 0, len(n)) 
   if (match.size!=0): 
      print ("Common Substring ::>",m[match.a: match.a + match.size])  
   else: 
      print ('No longest common sub-string found') 
# Driver program 
if __name__ == "__main__": 
   X = input("Enter first String ")
   Y = input("Enter second String ")
   matchsubstring(X,Y) 

出力結果

Enter first String pythonprogramming
Enter second String pro
Common Substring ::> pro

まとめ

SequenceMatcher を使えば、複雑なアルゴリズムを自前で実装することなく、わずか数行のコードで最長共通部分文字列を取得できます。文字列の類似度チェックや差分検出など、さまざまな場面で応用できる便利な手法なので、ぜひ活用してみてください。