最長重複文字列問題
Haskellでは,
文字列プログラミングの課題として,
たとえば,
Ask not what your country can do for you,
but what you can do for your country.
このフレーズの最長重複文字列は
この問題を取り上げる理由は,
- 注2)
- Jon Bentley著,
小林 健一郎訳, ピアソン・ エデュケーション, 2000年
接尾辞リストが問題を解く鍵
みなさんは,
問題を解く鍵となるのは,
Haskellでは,:module
コマンドのあとにモジュール名を入力します。技術的な理由は省きますが,-XNoMonomorphismRestriction
というオプションを指定してください。
% ghci -XNoMonomorphismRestriction
> :module Data.List
これで,
> tails "banana"
["banana","anana","nana","ana","na","a",""]
先頭が順に削られていった文字列のリストとは何かよくわかると思います。実は,
tails "banana"で作成されたリストにおいて,
- 注3)
- 関数の型や,
関数がどのモジュールで定義されているのかを知るには, Hoogleという検索サービスが便利です。 - 注4)
- モジュールを読み込むと,
プロンプトにモジュール名が追加されます。以降では省略して表記します。
解き方の指針
接尾辞リストが手に入れば,
- 接尾辞リストを作る
- ソートする
- 隣り合う要素を組にする
- 組となっている2つの文字列の共通部分の長さを求める
- 共通部分が一番長い要素を取り出す
- 共通部分のみを残す
この設計を入力の例とともに図示したのが図5です。入力例は"mississippi"であり,
また,
接尾辞リストを作る/ソートする
一番目の部品tailsや二番目の部品sortは,
隣り合う要素を組にする
次に隣り合う要素を組にする関数makePairを作りましょう。この実装には,
> let makePair xs = zip xs (tail xs)
使ってみましょう。
> makePair ["boo","foo","woo"]
[("boo","foo"),("foo","woo")]
文字列の共通している部分の長さを求める
文字列の共通している部分の長さを求める関数calcLenを作ります。calcLenは,
入力のリストが持つ要素は
共通部分の長さを測る
2つの文字列に対して共通部分の長さを求めるにはどうすればよいでしょうか? 例として,
> zip "word" "world"
[('w','w'),('o','o'),('r','r'),('d','l')]
この結果を見ると,
補助関数として第一要素と第二要素が等しいか調べる関数pairEqを定義します。
> let pairEq (x,y) = x == y
このように,
> let ret1 = zip "word" "world"
> takeWhile pairEq ret1
[('w','w'),('o','o'),('r','r')]
あとは,
> let comlen xs ys = length (takeWhile pairEq
(zip xs ys))
利用例を次に示します。
> comlen "word" "world"
3
関数calcLenを定義する
次に,
> let lenstr (xs,ys) = (comlen xs ys, xs)
使ってみましょう。
> lenstr ("word","world")
(3,"word")
lenstrができてしまえば,
> let calcLen = map lenstr