最長重複文字列問題

『珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造』の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

参考

• 第3章　リストと文字列―最長重複文字列問題で知るリストプログラミング：［入門］関数プログラミング―質の高いコードをすばやく直感的に書ける！