Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

最長重複文字列問題

『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』の15章2節で紹介されている「最長重複文字列問題」をRubyを使って解いてみました。

「最長重複文字列問題」とは、文字列の中からもっとも長い重複する文字列を見つけるという問題で、

  • "mississippi"なら"issi"
  • "Ask not what your country can do for you, but what you can do for your country."なら"can do for you"

になります。 アルゴリズムの詳細については、参考サイトがわかりやすいと思います。

max_dup_str.rb

実行結果

$ ./max_dup_str.rb
issi
 can do for you

参考