2

Aho-Corasick アルゴリズムのコードがあります。しかし、特定の文字列リスト内のテキストを検索するときに、検索手順中に状態情報を使用する方法をまだ理解していません。

たとえば、私は文字列のリストを持っていますが、リストにある[MOSCOW][COLA]かどうかを判断する必要がありCAます。リストにある場合、その位置は何ですか?

ここにコードへのリンクがあります。

4

1 に答える 1

2

あなたが研究しているアルゴリズムは、まったく逆の方法で機能します。辞書が[MOSCOW][COLA]で入力文字列がCAの場合、アルゴリズムは in のすべての場所と in のすべての場所を教えてくれMOSCOWます。CACOLACA

ここで、特定の状態 (または、リンクされたコードがそれを呼び出す場合) にはNode、次のような意味がありますCCOLAMOSCOW。(これは、 の最初の文字の後にアクセスされたノードである可能性がありますCA。)

アルゴリズムの能力は、別の入力、たとえば を検索するときに簡単に確認できますMOSCOLONI。が表示される直前にL、現在の状態は「可能性のある 5 文字MOSCOW、または可能性のある 2 文字になる可能COLA性がある」ことを意味します。実際、文字の繰り返しも考慮すると、すべての単語のすべての位置にさえ含まれます。

于 2012-07-18T17:41:50.417 に答える