![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2020-11-18T02:33:55+00:00","","") #author("2020-12-08T01:48:50+00:00","","") [[Rene_アルゴリズムとデータ構造]] *文字列照合 [#w84df3fb] **1. 文字列照合の解説 （30分） [#o1eaeba4] https://www.slideshare.net/kazumamikami1/ss-16964389 *ハッシュ探索法 [#w84df3fb] https://tech.retrieva.jp/entry/2020/05/21/134735 **1. ハッシュ探索法の解説 （30分） [#o1eaeba4] ***Knuth-Morris-Pratt法の理解 [#u71e252d] ***ハッシュ探索法の概要 [#s549186e] https://algoful.com/Archive/Algorithm/KMPSearch https://breezegroup.co.jp/202006/algorithm-search/ https://www.atmarkit.co.jp/ait/articles/0902/04/news144_2.html ***項目4, 5のハッシュ探索法と特長の理解 [#udef1b20] ***Boyer-Moore法の理解 [#m64f7d03] https://www.momoyama-usagi.com/entry/info/algo/search#%EF%BC%94%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E6%8E%A2%E7%B4%A2 https://algoful.com/Archive/Algorithm/BMSearch ***チェイン法とオープンアドレス法の理解 [#b152feb2] https://www.atmarkit.co.jp/ait/articles/0902/04/news144_3.html https://qiita.com/Hinako_800/items/611980b88f3631fa130c **2. 文字列照合のプログラム （20分） [#o1eaeba4] **2. ハッシュ探索法のプログラム （25分） [#o1eaeba4] ***KMP法を実行し確認 [#h831a428] ***プログラムリスト1とプログラムリスト2を実行し確認 [#h831a428] https://engineeringnote.hateblo.jp/entry/python/algorithm-and-data-structures/kmp_algorithm (python練習) http://www.nct9.ne.jp/m_hiroi/light/pyalgo04.html https://yottagin.com/?p=7218 (python練習) **3. 様々な時間計算量 （20分） [#q3acd514] ***BM法を実行し確認 [#fda67a56] ***例7のナベアツの計算量の求め方までを理解 [#h831a428] https://engineeringnote.hateblo.jp/entry/python/algorithm-and-data-structures/bm_algorithm (python練習) https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0 **3. 様々な文字列照合 （20分） [#q3acd514] **4. ハッシュ探索法の時間計算量 （15分） [#j52d31b9] ***KMP法とBoyer-Moore法の違いを理解 [#h831a428] ***チェイン法の性能1, 性能2までを理解 [#h831a428] http://www-ikn.ist.hokudai.ac.jp/~kida/lecture/alg2018-ex1.pdf http://www.ibe.kagoshima-u.ac.jp/~fuchida/lecture/algorithm/alg08-%E6%8E%A2%E7%B4%A2%E3%81%A8%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5.pdf https://ikatakos.com/pot/programming_algorithm/string_search **4. Pythonの標準モジュールの活用 （20分） † [#jc4e41d2] https://note.nkmk.me/python-str-search/
