一覧
border とは？
border とは？
ある文字列の prefix と suffix が一致している場合の、一致している prefix と suffix
・ある文字列の prefix と suffix が一致している場合、一致している prefix と suffix をその文字列の border と呼ぶ
・但し、prefix と suffix は重複する部分があってもよいが一致していてはいけない
・border が空文字でも OK
・空文字には border が存在しない
・最も幅広い border を tagged border と呼ぶ
tagged borderの具体例
ababaa
・a
Knuth-Morris-Pratt algorithm
文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
string - Knuth–Morris–Pratt algorithm: border array - Stack Overflow
Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search) - YouTube
algorithm - Finding the longest border of a string - Stack Overflow
Knuth-Morris-Pratt algorithm - コードの恵み
Knuth-Morris-Pratt algorithm
・MP法とKMP法の違い
Knuth-Morris-Pratt algorithm
http://winnie.kuis.kyoto-u.ac.jp/members/okuno/Lecture/02/DataStructure/ds-02-13.pdf
感想
2018/3/10
10ヶ月経過
・ようやく最低限の動作確認が出来た
・KMPの根本的な理解は全然出来ていないが、少なくともこうすればKMP法で求められるという最低限のコピペは出来るようになった(内容は理解できていないけれども)
最低限の理解が出来るようになるまで時間がかかった理由
・インターネットに掲載されている内容が、サイト毎に異なる
・KMP法として説明されている内容のほとんどがMP法を解説したもの
・インターネットだけではなく、書籍の中でもKMP法と称してMP法を紹介しているものもある
・インターネットに掲載されている大学の講義資料でも同様
・レーベンシュタインを学習した際も苦労したが、解説内容がサイト毎に異なると初学者は非常に困る
・ネットに掲載されている情報が微妙に異なる例としては色変換もそう。こちらも未だに違いを理解できていない
今回気が付いたこと
・KMP法はMP法の先にある考え方
・MP法を理解してから、KMP法を学習したほうが良い
MP法の考え方
・割合簡単
KMP法の考え方
・超絶難しい
・KMP法は、MP法の計算結果を元に、さらなる計算を行っている
・計算方法はコピペ出来たが、その意味は未だ理解できていない
2018/3/15
最低限の動作確認を出来たと思ったが、甘かったかも
・「篠原研究室」と「Université de Rouen」で異なる結果を返す場合があることに気が付く
・何れが正しいの？ あるいは両方とも正なの？
2018/3/20
今日確認したら両方とも合っていた
・「篠原研究室」のコードが変更されたのかな？ と思い確認したが以前と同じだった
・何か勘違いしている？
・単に疲れていたから見間違えただけ？
・まあでも、合っているなら、それに越したことはない
2018/3/23 → 2018/5/7
詳しそうだけれども具体的な事例が未掲載なため、正しいか否か判断不能
・JAIST 北陸先端科学技術大学院大学
内容が期待した結果とあまりに乖離している
・理解できないため、とりあえず見なかったことにする
・和歌山大学
・山梨大学
・
・KMP法が分からないので調べているのですが
・KMP法の移動量テーブルについて