「文字列を先頭から見て同じところまで除去」をやってみた


文字列を先頭から見て同じところまで除去」を Haskell でやってみました。

お題は以下の通りです。

複数の文字列を受け取り、受け取った文字列をそれぞれ先頭から見てゆき、すべてが同じ内容であれば除去した内容の文字列を返却する関数を書いて下さい。
※関数の引数と戻り値については複数の文字列が受け渡しできれば型や方法は問いません*1。

例1)hoge("abcdef", "abc123")
戻り値 => "def" と "123" ("abc" が除去される)

例2)hoge("あいうえお", "あいさんさん", "あいどる")
戻り値 => "うえお", "さんさん", "どる" ("あい" が除去される)

例3)hoge("12345", "67890", "12abc")
戻り値 => "12345", "67890", "12abc" (一致なしのため、そのまま返却される)

*1:文字列配列で受け取り、文字列配列で返却するなど。

何も考えずに愚直に書いたらこうなったという感じです。効率とかも全然気にしていません。もっとスマートに書けるようになりたいですね。

f s = all $ (==s) . take (length s)
g = map reverse . scanl (flip (:)) []
h (x:xs) = last $ takeWhile (flip f xs) (g x)
hoge xs = map (drop (length (h xs))) xs

例題 3 つの出力は以下の通り (Ideone.com)。

["def","123"]
["\12358\12360\12362","\12373\12435\12373\12435","\12393\12427"]
["12345","67890","12abc"]

ひらがなの文字がちゃんと表示されていないのはご愛嬌ということで。一応先頭の文字は正しく取り除かれています。

解説

以下の考え方で組み立てています。

  1. ある文字列が,リスト中の文字列の先頭に全部一致しているかを判定 (例えば,文字列 "ab" とリスト ["abc", "abab"] なら True, "ho" と ["hoge", "piyo"] なら False など)。
  2. 文字列を構成する文字列を先頭から抽出 (対象とする文字列が "foo" なら ["", "f", "fo", "foo"])。
  3. リストの先頭要素から 2 の部分文字列のリストを抽出, 1 で判定を行い最長のもの (最後の要素) を取得。
  4. 3 で得た文字列を,リストの全要素から取り除く。

1, 2, 3, 4 がそれぞれ回答中の関数 f, g, h, hoge に相当します。

ちなみにお題は文字列に限定していますが, hoge の型は (Eq a) => [[a]] -> [[a]] なので,文字列以外にも利用可能です。

更新履歴

  • [2011-08-13 19:20+0900] 問題文の引用,簡単な解説の追加。