-1

I understand the algorithm of pattern matching with a Text T of length n and a Pattern P of length m is linear using the witness table algorithm.

I also know how to construct the witness table in m^2 time but there is an algorithm of O(m) for constructing the table that I don't understand.

Please help.

4

2 に答える 2

2

パート I パート II - 正しさ

Amihood Amir コンピューター サイエンス教授。

(このデータは私のものではありません)。

于 2012-08-28T20:06:45.857 に答える
1

ここを見た方がいい

KMPアルゴリズムや実行時解析について解説しています。

于 2012-08-24T10:11:29.947 に答える