ここでは、文字列検索アルゴリズムの一種 である KMP法 の python3 での実装例をご紹介します。
文字列 S から単語 P を探し、S 中に P が含まれる場合、S における一致位置の（先頭の）インデックスをリストで返します（つまり、P が S 内に複数ある場合を想定しています）。
S = "isawsquirrelnearmysquirrelababhouseoh"
P1 = "my"
P2 = "squirrel"
P3 = "ab"
def createTable(pattern):
m = len(pattern)
pattern_table = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = pattern_table[j-1]
if pattern[i] == pattern[j]:
j += 1
pattern_table[i] = j
return pattern_table
def kmpSrach(string, pattern):
n, m = len(string), len(pattern)
res_table = []
pattern_table = createTable(pattern)
j = 0 # p内の参照index
for i in range(n):
while j > 0 and string[i] != pattern[j]:
j = pattern_table[j-1]
if string[i] == pattern[j]:
j += 1
if j == len(pattern):
res_table.append(i - m + 1)
j = pattern_table[j - 1]
return res_table
res1 = kmpSrach(S, P1)
print(res1) # --> [16]
res2 = kmpSrach(S, P2)
print(res2) # --> [4, 18]
res3 = kmpSrach(S, P3)
print(res3) # --> [26, 28]
お役に立てれば幸いです！