6
计算所有后缀的排名
source link: http://maskray.me/blog/2012-01-08-ranking-suffixes
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
计算所有后缀的排名
占位。以后补上解释。
Prefix-doubling algorithm。
import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.Instances
import Data.Array
import Data.Function
import Data.List
rank :: (Ord a) => [a] -> [Int]
rank = elems . liftM2 array ((,) 0 . pred . length) (map (first snd) . concat . label . groupBy ((==) `on` fst) . sort . flip zip [0..])
where
label = zipWith (flip (map . flip (,))) <*> scanl (+) 0 . map length
rankTails1 :: (Ord a) => [a] -> [Int]
rankTails1 = liftM3 applyUntil (((and . elems).) . (.flip zip (repeat True)) . accumArray (||) False . (,) 0 . pred . length) (const $ map reorder (iterate (*2) 1)) rank
where
reorder = (rank.) . (zip <*>) . ((++ repeat (-1)).) . drop
applyUntil p fs x = head . dropWhile (not . p) $ scanl (flip ($)) x fs
main = getLine >>= print . rankTails1
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK