Manacherアルゴリズムによる回文解析の効率的処理
問題の背景
文字列 s が与えられ、その中にある最長の連続する回文部分文字列の長さを求めたいとします。単純なアプローチとしては、すべての部分文字列を列挙し、それぞれが回文かどうかを判定する方法がありますが、これは O(n^3) の計算量となり非効率です。
より良い方法として、各位置を中心として左右に拡張していく O(n^2) アルゴリズムが考えられます。この方法で ...
6月8日 23:54 投稿
奇想天外なアイデアがコードで現実になる場所
6月8日 23:54 投稿