質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

1回答

961閲覧

KMP法の最悪のループの繰り返し回数はなぜ2*|S|なんでしょうか?

zuttonetetai

総合スコア1

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2022/03/22 23:20

編集2022/03/23 16:18

KMP法のループの繰り返し回数について質問があります。
教科書やwikipediaなどで勉強しておりますと、KMP法のループの繰り返しは、テキストSの長さを|S|とすると
最悪でも繰り返しの回数は
2*|S|となるとあります。

なぜこうなるのかが、理解できないのですが、どなたかわかりやすくご教授いただけないでしょうか?

追記

-Wikipediaから引用-

テーブル T が事前に用意されているとした場合、クヌース-モリス-プラット法の検索部分の計算量は O(k)(ここで k は S の長さ)となる。関数呼び出しに関わる固定オーバヘッド部分を除くと、全ての計算は while ループ内で行われるため、このループの繰り返し回数の上限が計算量となる。ここで T の性質が重要となる。S[m] から開始された照合が S[m + i] と W[i] の不一致で失敗したとき、次の照合は S[m + (i - T[i])] から開始される。次の照合は m 以降のインデックスから開始される必要があるため、T[i] < i が成り立つ。

このことから、ループが最大 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 となっているはずである。従っていずれにしても処理は終了する。

以上からループの繰り返し回数は最大でも 2k 回であり、この検索アルゴリズムの計算量は O(k) となる。

---①の所でループの終了条件はi+m=kとなっていて、一回ループを回すごとにi またはi+mが増えるのであれば、繰り返す回数はkだと思ってしまいます。
m=0の時、iが0〜kまで増えたらループの終了条件に達して繰り返す回数はkだと思います、どういうふうに考えれば2kになるのでしょうか?

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

maisumakun

2022/03/22 23:25

> なぜこうなるのかが、理解できないのですが いま現在、自分なりに考えて、これとは違う上限だと考えている、ということでしたら、その詳細をご提示ください。
SaitoAtsushi

2022/03/23 02:41

Wikipedia の解説はとても丁寧です。 あらためて解説してもこれよりわかりやすくはなりません。 理解できないのであれば前提知識が不足しているか、つまらない思い違いをしているかです。 質問者の頭の中でどんな知識が不足しているのかどこで躓いているのかはわかりようがないので、思考過程をたどれるだけの詳細が必要です。
guest

回答1

0

一回ループを回すごとにi またはi+mが増えるのであれば

そうではありません。「i - T[i]mに加算」したあとに、iT[i]に置き換えていますので、この分岐ではm + iの値は変化しません

投稿2022/03/23 07:18

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問