レトリバのCTOの武井です。
https://twitter.com/goth_wrist_cut
新型コロナウィルスが世界で猛威を振るっていますが、皆様安全に過ごせておりますでしょうか。
レトリバでは フルリモート化 や、
交流なども オンライン飲み会 にするなど、工夫して過ごしています。
さて、今回はそんな新型コロナウィルス、COVID-19の遺伝子配列をターゲットに、
Longest Common Substring(最長共通部分文字列)を求めたり、そのアルゴリズムの解説をしてみようと思います。
アルゴリズムの説明自体は William Fiset さんという方が動画で説明しており、
非常に分かりやすい図示がありますので、是非ご覧になって下さい。
https://www.youtube.com/watch?v=Ic80xQFWevc
https://www.youtube.com/watch?v=DTLjHSToxmo
このブログでは日本語での解説と、実際の実装まで踏み込んで紹介しています。
- はじめに
- Longest Common Substrings(最長共通部分文字列)とは
- Suffix Array と LCS
- LCSの制約条件
- 共通部分文字列の長さ
- Slide Window
- 道具立て
- CardinarityQueue(異なり数カウントキュー)
- MinQueue(最小値キュー)
- SlidingWindow
- コードと解説
- まとめ
続きを読む