質問編集履歴
1
躓いているところを具体的に質問しておらず申し訳ありませんでした。具体的に疑問に思っている所をWikipediaの内容を引用して書いてみましたので、ご教授頂けたら幸いです。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -5,3 +5,18 @@
|
|
|
5
5
|
|
|
6
6
|
なぜこうなるのかが、理解できないのですが、どなたかわかりやすくご教授いただけないでしょうか？
|
|
7
7
|
|
|
8
|
+
|
|
9
|
+
追記
|
|
10
|
+
|
|
11
|
+
-Wikipediaから引用-
|
|
12
|
+
|
|
13
|
+
テーブル T が事前に用意されているとした場合、クヌース-モリス-プラット法の検索部分の計算量は O(k)（ここで k は S の長さ）となる。関数呼び出しに関わる固定オーバヘッド部分を除くと、全ての計算は while ループ内で行われるため、このループの繰り返し回数の上限が計算量となる。ここで T の性質が重要となる。S[m] から開始された照合が S[m + i] と W[i] の不一致で失敗したとき、次の照合は S[m + (i - T[i])] から開始される。次の照合は m 以降のインデックスから開始される必要があるため、T[i] < i が成り立つ。
|
|
14
|
+
|
|
15
|
+
このことから、ループが最大 2k 回繰り返されることがわかる。繰り返しのたびにループ内の2つの分岐のいずれかが実行される。最初の分岐では、常に i をインクリメントして m をそのままとし、インデックス m + i を変化させることで S 内の文字を調べていく。次の分岐では i - T[i] を m に加算する。前述の通り、この加算する値は常に正の値である。従って、照合開始位置 m は増加していく。ループの終了は m + i = k となったときである。---① 従ってループ内の各分岐は k 回実行され、各分岐は m + i か m のいずれかを増加させる。ここで、m ≤ m + i である。m = k となったとき、m + i ≥ k なので、それ以前のいずれかの時点で m + i = k となっているはずである。従っていずれにしても処理は終了する。
|
|
16
|
+
|
|
17
|
+
以上からループの繰り返し回数は最大でも 2k 回であり、この検索アルゴリズムの計算量は O(k) となる。
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
---①の所でループの終了条件はi+m=kとなっていて、一回ループを回すごとにi またはi+mが増えるのであれば、繰り返す回数はkだと思ってしまいます。
|
|
22
|
+
m=0の時、iが0〜kまで増えたらループの終了条件に達して繰り返す回数はkだと思います、どういうふうに考えれば2kになるのでしょうか？
|