WEB+DB PRESS Vol.67の最長重複文字列問題をClojureで解いてみた

今月発売のWEB+DB PRESS Vol.67には関数プログラミングの特集があり，主にHaskellで解説された入門記事が載っています．その今月号を少し早く手に入れることができたので，早速記事の中で解説されているプログラムの中から「最長重複文字列問題」をClojureで解いてみました．珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造でも取り上げられている問題です．

WEB+DB PRESSに載っているコードの設計図通りに順序立てて並べています．実際に実行してみると，

user> (longest-duplicated-substring "mississippi")
(4 "issi") 

user> (longest-duplicated-substring "Ask not what your country can do for you, but what you can do for your country.")
(15 " can do for you")

といったように，ある文字列の中で重複している最も長い文字列が出力されます．

ただ，このスクリプトでは例で出されていた短い文字列を処理するだけの目的で実装したので，長い文字列の場合にはとたんに大量のメモリが必要になるため注意が必要です．今の自分のレベルでは遅延シーケンス周りが不勉強であまり理解できていないので，この実装では組み込めませんでした...．このあたりは関数プログラミングの腕の見せ所といったところだと思うので，もう少し理解を深めたら再度実装しなおしてみたいです．まあ，取り敢えず今のところはこれでいいかなという感じです．早く初心者を抜けて中級者くらいになりたいところですね．

参考

• http://www.mew.org/~kazu/material/2011-fp.pdf
• http://www.cs.bell-labs.com/cm/cs/pearls/sec152.html

WEB+DB PRESS Vol.67

珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造