# Optimize calculation of string self-similarly with its suffixes

I am trying to solve a Hacker Rank problem about string suffixes:

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.

Calculate the sum of similarities of a string S with each of its suffixes.

I have the following code:

import System.IO
import Data.Maybe
import Data.List
import qualified Data.ByteString.Char8 as BSC

main = do
n <- liftM getIntFromBS BSC.getLine
replicateM_ n $do s <- BSC.getLine putStrLn . show$ sum $map (cntPrefix s)$ tail $sort$ BSC.tails s
where
cntPrefix str pref = length $takeWhile (\t -> fst t == snd t)$ BSC.zip pref str


But performance is really bad. I am doing this challenges to learn Haskell and thus my skills aren't good enough to optimize this program. Any help is appreciated.

As far as I can tell your solution is not only slow but incorrect because of your usage of sort. Dropping that single function from your pipeline nets an exponential improvement, and it stopped including the similarity of s to itself in the answer.

Make sure also you're compiling with -O2, otherwise sum won't be optimized into a strict fold and you'll blow up the stack with thunks.

I also came up with a version targeted toward readability, but it's ~3x slower than your (corrected) ByteString based version so I'll just include it here as a curiosity.

import Control.Monad (replicateM_)
import Data.List (tails)

main :: IO ()
main = do
replicateM_ n $do s <- getLine print$ sum $map (similarity s) (suffixes s) similarity :: (Eq a) => [a] -> [a] -> Int similarity s = length . takeWhile id . zipWith (==) s suffixes :: [a] -> [[a]] suffixes = tail . tails  • The sort isn't there for fun, is necessary to give the correct answer. Your answer gives wrong output. – OneEyeQuestion Nov 13 '14 at 14:21 • Only if you consider xs :: [a] to be a suffix of xs :: [a], which depends on how pedantic you're willing to be. It also is completely unnecessary, because the only thing tail . sort . tails will ever do is drop an instance of the empty list which in your case would have a similarity of 0 anyway and not affect the sum. Remove tail$ sort \$ from your version and you'll see the answer you expect along with the speedup. – bisserlis Nov 13 '14 at 14:50