kmp法のパターン側インデックスの更新について

kmp法の勉強をしている中で、以下のコードをサンプルとして参考にしました。

python
1
2def  kmp_macth(txt: str, pat: str) -> int:
3    # skip_tableの作成
4    pt = 1 # 照合対象のインデックスをなぞるカーソル
5    pp = 0 # 照合したいパターンをなぞるカーソル
6    skip = [0] * (len(pat)+ 1)
7    
8    skip[pt] = 0
9    while pt != len(pat):
10        if txt[pt] == pat[pp]:
11            skip[pt] == pp + 1
12            pt += 1
13            pp += 1
14        elif pp == 0:
15            skip[pt] = 0
16            pt += 1
17        else:
18            pp = skip[pp] #####
19
20    # ここから一致文字列の探索
21    pt = 0
22    pp = 0
23    while pt != len(txt) and pp != len(pat):
24        if txt[pt] == pat[pp]:
25            pt += 1
26            pp += 1
27        elif pp == 0:
28            pt += 1
29        else:
30            pp = skip[pp] #####
31
32    return pt - pp if pp == len(pat) else -1
33
34if __name__ == "__main__":
35    s1 = input("テキスト：")
36    s2 = input("パターン：")
37
38    idx = kmp_macth(s1, s2)
39
40    if idx == -1:
41        print("テキスト中にパターンは存在しない")
42    else:
43        print(f'{(idx + 1)}文字目にマッチ')

このコードの#####の箇所ですが、パターンのカーソルを更新していることはわかります。
しかし、どちらも常に
pp = 0
になるのではないでしょうか。このコードでは、テーブルの作成・一致文字列の探索どちらにおいても、#####の箇所は、パターンの先頭からの照合をすることになるように思えてなりません。
参考書のサンプルコードなので、自分が間違っているのだろうと思い、pp = 0ではうまくいかないケースを探すのですがうまく見つかりません。
どなたか、pp = skip[pp]でないと上手くいかないケースを教えていただけないでしょうか。

行動規範の内容に同意します

回答2件

テーブル作成の段階でtxtとの一致をみているのはおかしいです。テーブルはパターン側のみの情報で作ります。
そこからおかしいので思った結果にならないんでしょう。

Text
1aaab
2aab

この組み合わせで検索がうまく行えてるか試してみてください。

投稿2021/05/29 05:53

yudedako67

総合スコア2047

fu_3823

2021/05/29 21:15

ありがとうございます。そもそもの違いから訂正してみます。理解不足の質問で申し訳ありませんでした。

行動規範の内容に同意します

ベストアンサー

コードが間違っています。

diff
1 def  kmp_macth(txt: str, pat: str) -> int:
2     # skip_tableの作成
3     pt = 1 # 照合対象のインデックスをなぞるカーソル
4     pp = 0 # 照合したいパターンをなぞるカーソル
5     skip = [0] * (len(pat)+ 1)
6
7     skip[pt] = 0
8     while pt != len(pat):
9-        if txt[pt] == pat[pp]:
10-            skip[pt] == pp + 1
11+        if pat[pt] == pat[pp]:
12+            skip[pt] = pp + 1
13             pt += 1
14             pp += 1
15         elif pp == 0:
16             skip[pt] = 0
17             pt += 1
18         else:
19-            pp = skip[pp] #####
20+            pp = skip[pp-1] #####
21
22     # ここから一致文字列の探索
23     pt = 0
24     pp = 0
25     while pt != len(txt) and pp != len(pat):
26         if txt[pt] == pat[pp]:
27             pt += 1
28             pp += 1
29         elif pp == 0:
30             pt += 1
31         else:
32-            pp = skip[pp] #####
33+            pp = skip[pp-1] #####
34
35     return pt - pp if pp == len(pat) else -1