[Python] クヌース–モリス–プラット法

クヌース–モリス–プラット法

クヌース–モリス–プラット法（Knuth–Morris–Pratt algorithm、KMP法と略記）とは、文字列検索アルゴリズムの一種。テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

決定性有限オートマトンの文字列検索と比較すると、状態遷移表を事前に作成するのではなく、パターンの接頭語と接尾語の一致を示す表を事前に作成することで、計算量を減らします。

総当たりの文字列検索と比較すると、 パターンの接頭語と接尾語の一致を示す表を用いることで、無駄な後戻りを防ぐことができ、計算量が減ります。

以下の動画を参考にしています。

また、以下分かりやすいです。

文字列の中から効率良くキーワードを探し出せ (2/4)

import random
import string

def _prefix_table(pattern):
    
    m = len(pattern)
    pi = [0] * m
    k = 0

    for q in range(1, m):
        while k > 0 and pattern[k] != pattern[q]:
            k = pi[k - 1]
        if pattern[k] == pattern[q]:
            k = k + 1
        pi[q] = k
    
    return pi

def match_pattern_kmp(text, pattern):
    n = len(text)
    m = len(pattern)
    prefix_table = _prefix_table(pattern)
    q = 0

    for i in range(n):
        while q > 0 and pattern[q] != text[i]:
            q = prefix_table[q - 1]
        if pattern[q] == text[i]:
            q = q + 1
        if q == m:
            return i - m + 1

    return -1

def print_match_pattern_result(text, pattern):
	index =  match_pattern_kmp(text, pattern)
	if index>=0:
		print(f'"{pattern}"は {index}番目に見つかりました。')
	else:
		print(f'"{pattern}"は見つかりません。')


random.seed(1)
target_str = ''.join(random.choices(string.ascii_letters + string.digits, k=20))
# i0VpEBOWfbZAVaBSo63b
print(target_str)
# "BSo63"は 14番目に見つかりました。
print_match_pattern_result(target_str, "BSo63")
# "BSo6E"は見つかりません。
print_match_pattern_result(target_str, "BSo6E")