[Python] 文字列のブルートフォース探索

与えられた文字列の中から、パターンに一致する部分を総当たりで探します。

時間計算量は \( O(n \times m) \)、空間計算量は\( O(1) \) になります。

import random
import string

def match_pattern_bruteforce(target_str, pattern):
    for i in range(len(target_str) - len(pattern) + 1):
        str_i = i
        pattern_i = 0
        while str_i < len(target_str) and pattern_i < len(pattern) and target_str[str_i] == pattern[pattern_i]:
            str_i += 1
            pattern_i += 1
        if pattern_i == len(pattern): 
            return i
    return False

def print_match_pattern_result(target_str, pattern):
    index =  match_pattern_bruteforce(target_str, pattern)
    if index:
        print(f'"{pattern}"は {index+1}番目に見つかりました。')
    else:
        print(f'"{pattern}"は見つかりません。')


random.seed(1)
target_str = ''.join(random.choices(string.ascii_letters + string.digits, k=20))
# i0VpEBOWfbZAVaBSo63b
print(target_str)
print_match_pattern_result(target_str, "BSo63")

print_match_pattern_result(target_str, "BSo6E")