最長重複文字列問題

Haskellでは，文字のリストが文字列でした。整数のリストよりも文字列のほうが親しみが湧きやすいと思いますので，リストプログラミングの例として文字列プログラミングを取り上げます。文字列が文字のリストではない言語もありますが，ここで学ぶ考え方はそのまま通用すると思います。

文字列プログラミングの課題として，『⁠珠玉のプログラミング』（⁠注2）の15章2節に載っている「最長重複文字列」問題を取り上げましょう。これは，読んで字のごとく，最も長く重複している部分文字列を探す問題です。

たとえば，ケネディ大統領の就任演説の中で有名なフレーズで考えてみましょう。

Ask not what your country can do for you,
but what you can do for your country.

このフレーズの最長重複文字列は「can do for you」です。

この問題を取り上げる理由は，問題自体が実践的で興味深く，また問題に適したデータ構造を使うと問題解決が簡単になる例として秀逸だからです。今回，関数プログラミングで解いていきますが，前記の本には命令プログラミングの解法が載っていますから，必要であれば見比べることもできます。

注2）

Jon Bentley著，小林 健一郎訳，ピアソン・エデュケーション，2000年

接尾辞リストが問題を解く鍵

みなさんは，この問題をどうやって解くでしょうか？ この問題に初めて出会ったのなら，かなり難しいと思います。

問題を解く鍵となるのは，接尾辞リスト（あるいは接尾辞配列）というデータ構造です。あるリストに対する接尾辞リストとは，そのリストの先頭を順に削っていったリストを要素として持つリストのことです。言葉で説明してもわかりにくいと思いますので，Haskellに接尾辞リストを作らせてみましょう。

Haskellでは，Data.Listモジュールのtailsが接尾辞リストを作る関数です（注3⁠）⁠。対話環境でモジュールを読み込むには，:moduleコマンドのあとにモジュール名を入力します。技術的な理由は省きますが，この章のこれ以降，GHCiを起動する際に-XNoMonomorphismRestrictionというオプションを指定してください。

% ghci -XNoMonomorphismRestriction
> :module Data.List

これで，tails関数が使えるようになりました（注4⁠）⁠。文字列bananaの接尾辞リストを作ってみましょう。

> tails "banana"
["banana","anana","nana","ana","na","a",""]

先頭が順に削られていった文字列のリストとは何かよくわかると思います。実は，接尾辞リストは永続データであるリストととても相性が良いのです。図4を見てください。文字列bananaのどこもコピーしていないことがわかります。

tails "banana"で作成されたリストにおいて，たとえば"nana"は3番目に現れています。図4で"nana"に対応するのは，上段の左から3番目の四角です。この四角の下向きの矢印は，"nana"というリストを指していますね。

注3）

関数の型や，関数がどのモジュールで定義されているのかを知るには，Hoogleという検索サービスが便利です。

注4）

モジュールを読み込むと，プロンプトにモジュール名が追加されます。以降では省略して表記します。

解き方の指針

接尾辞リストが手に入れば，この最長重複文字列問題を解くのはそれほど難しくはありません。解き方の指針を示します。

• 接尾辞リストを作る
• ソートする
• 隣り合う要素を組にする
• 組となっている2つの文字列の共通部分の長さを求める
• 共通部分が一番長い要素を取り出す
• 共通部分のみを残す

この設計を入力の例とともに図示したのが図5です。入力例は"mississippi"であり，答えである出力は"issi"となっています。

また，図5には各部品に対し，これから作る関数の名前と型を書き込んであります。ある部品の出力の型が，次の部品の入力の型と一致していることを確かめておいてください。

接尾辞リストを作る／ソートする

一番目の部品tailsや二番目の部品sortは，Data.Listライブラリで提供されています。sortに文字列のリストが渡された場合は，辞書順に整列します。

隣り合う要素を組にする

次に隣り合う要素を組にする関数makePairを作りましょう。この実装には，常套手段があります。xsが与えられた場合，tail xsとzipを取ればよいのです。

> let makePair xs = zip xs (tail xs)

使ってみましょう。

> makePair ["boo","foo","woo"]
[("boo","foo"),("foo","woo")]

文字列の共通している部分の長さを求める

文字列の共通している部分の長さを求める関数calcLenを作ります。calcLenは，大まかにいうとリストを取ってリストを返すので，要素を変換することになります。

入力のリストが持つ要素は「文字列」と「文字列」の組でした。重複文字列を求めるのですから，この共通部分が欲しいのですが，あとで最も長いものを選び出せるように，共通部分の長さを計算しましょう。また，どちらかの文字列を残しておきましょう。どちらにも同じ共通部分があるので，どちらを残してもかまいませんが，ここでは前者を残すことにします。つまり出力のリストの要素は，「⁠共通部の長さ」と「前者の文字列」の組になります。

共通部分の長さを測る

2つの文字列に対して共通部分の長さを求めるにはどうすればよいでしょうか？ 例として，wordとworldを考えます。リストが2つあるので，常套手段としてzipを取ってみましょう。

> zip "word" "world"
[('w','w'),('o','o'),('r','r'),('d','l')]

この結果を見ると，第一要素と第二要素が等しい組だけ取り出したリストを新たに作り，その長さを測ればよいとわかります。リストの先頭から，ある条件に合致する間，要素を取り出して新たにリストを作るには高階関数takeWhileが使えます。

補助関数として第一要素と第二要素が等しいか調べる関数pairEqを定義します。

> let pairEq (x,y) = x == y

このように，組もパターンとして使えます。pairEqとtakeWhileを使ってみましょう。

> let ret1 = zip "word" "world"
> takeWhile pairEq ret1
[('w','w'),('o','o'),('r','r')]

あとは，このリストの長さを測るだけですから，共通の長さを測る関数comlenは次のように定義できます。リストの長さを測るには前出のlengthが使えます。

> let comlen xs ys = length (takeWhile pairEq
(zip xs ys))

利用例を次に示します。

> comlen "word" "world"
3

関数calcLenを定義する

次に，「⁠文字列」と「文字列」の組を取り，「⁠共通部分の長さ」と「第一要素の文字列」の組を返す関数lenstrを定義します。

> let lenstr (xs,ys) = (comlen xs ys, xs)

使ってみましょう。

> lenstr ("word","world")
(3,"word")

lenstrができてしまえば，あとはこの関数を入力リストにmapするだけです。そこで，calcLenは次のように定義できます。

> let calcLen = map lenstr