2021-01-30から1日間の記事一覧
今まで文字列照合系問題は、DP(LCS)で頑張っていたけど、持っていたら便利そうだと思ったのでライブラリを用意してみた。 前提 Z-Algorithmとは、最長共通接頭辞の長さを線形時間で求めるアルゴリズム。 文字列の長さをnとして、O(n2)を、O(n)に改善できる …
今まで文字列照合系問題は、DP(LCS)で頑張っていたけど、持っていたら便利そうだと思ったのでライブラリを用意してみた。 前提 Z-Algorithmとは、最長共通接頭辞の長さを線形時間で求めるアルゴリズム。 文字列の長さをnとして、O(n2)を、O(n)に改善できる …