suffix array(2)

結構前に書いた、suffix_arrayの記事の続き。

文字列とその部分文字列を入力して、
部分文字列が出現する位置を列挙する

ということで、以前書いた関数をそのまま組み立てるだけで出来ちゃう。

import Data.List

maketouple :: Int -> [String]->[(String , Int)]
maketouple n [s] = [(s , n)]
maketouple n (s:str) = (s,n):maketouple (n+1) str

suffix_index :: String -> [Int]
suffix_index = map snd.sort.maketouple 0.init.tails

search :: [String] -> [Int]
search (str:k:_) = map snd.filter ((k `isPrefixOf`).fst)
                              .maketouple 0$tails str

main = getLine >>= print.search.take 2.words

実行例

abjbeahbajpbhvjajsf aj   
[8,15]