Pythonでのクヌース・モリス・プラット法の実装

Pythonでのクヌース・モリス・プラット法の実装クヌース・モリス・プラット法 (Knuth-Morris-Pratt algorithm) は、部分文字列検索において、与えられた文字列の中に特定のパターンが現れるかどうかを効率的に調べるアルゴリズムです。このアルゴリズムは、O(n + m) の時間計算量を持ち、n は検索対象の文字列の長さ、m は検索するパターンの長さです。ここでは、Pythonを用いてクヌース・モリス・プラット法を実装する方法について説明します。

クヌース・モリス・プラット法とは

まず、クヌース・モリス・プラット法の概要を説明します。このアルゴリズムは、検索するパターンのプレフィックス (接頭辞) とサフィックス (接尾辞) の一致に着目します。例えば、"ABCDABD" という文字列において、パターン "ABD" の場合、プレフィックス "A" とサフィックス "D" の一致を探すことで、次に比較するべき位置を決定します。

Pythonでのクヌース・モリス・プラット法の実装

次に、Pythonでの実装方法について説明します。以下は、クヌース・モリス・プラット法を実装した関数の例です。

def kmp_search(pattern, text):
    m = len(pattern)
    n = len(text)
    lps = [0] * m
    j = 0
    compute_lps_array(pattern, m, lps)
    i = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            print("Found pattern at index " + str(i-j))
            j = lps[j-1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1

def compute_lps_array(pattern, m, lps):
    len = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            if len != 0:
                len = lps[len-1]
            else:
                lps[i] = 0
                i += 1

この関数では、引数としてパターン (pattern) と検索対象の文字列 (text) を受け取り、パターンが現れた場所のインデックスを表示します。lps (Longest Proper Prefix Suffix) は、プレフィックスとサフィックスの一致を示す配列で、compute_lps_array関数によって事前に計算されます。関数内では、iはtextのインデックス、jはpatternのインデックスを表し、iとjを1つずつ進めながら、一致する文字があるかどうかを調べます。jがパターンの長さmと等しくなると、パターンが現れた場所のインデックスを表示し、jをlps[j-1]で更新します。このようにすることで、パターンの一部が一致しなかった場合でも、以前に一致していた部分の情報を利用して、比較をスキップできるようになっています。

compute_lps_array関数では、パターンのプレフィックスとサフィックスの一致を示すlps配列を計算します。iはパターンのインデックスを表し、lenはlps[i]の値を保持します。iを1つずつ進めながら、パターンの文字列を比較して、一致している場合はlenをインクリメントし、lps[i]にlenの値を代入します。一致していない場合は、lenを更新するか、lps[i]に0を代入します。以上が、Pythonでのクヌース・モリス・プラット法の実装についての説明です。以下は、この関数を使用した例です。

text = "ABCABCDABDABCABCDABDABCDABDE"
pattern = "ABD"
kmp_search(pattern, text)

この例では、パターン "ABD" がテキスト文字列の中で2箇所に現れています。関数の出力は次のようになります。

Found pattern at index 3
Found pattern at index 18

このように、クヌース・モリス・プラット法を用いることで、文字列の中から特定のパターンを効率的に検索することができます。

完全なコードの例

以下に、完全なPythonコードを示します。

def compute_lps_array(pattern):
    """
    Compute the LPS (Longest Prefix Suffix) array for the given pattern
    """
    m = len(pattern)
    lps = [0] * m
    len = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            if len != 0:
                len = lps[len-1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(pattern, text):
    """
    Search for occurrences of the given pattern in the given text using the KMP algorithm
    """
    n = len(text)
    m = len(pattern)
    lps = compute_lps_array(pattern)
    i = 0  # index for text[]
    j = 0  # index for pattern[]
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            print("Found pattern at index", i-j)
            j = lps[j-1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1

text = "ABCABCDABDABCABCDABDABCDABDE"
pattern = "ABD"
kmp_search(pattern, text)