Optimize calculation of string self-similarly with its suffixes
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
        n &lt;- readLn
        replicateM_ n $ do
            s &lt;- getLine
            print $ sum $ map (similarity s) (suffixes s)

similarity :: (Eq a) =&gt; [a] -&gt; [a] -&gt; Int
similarity s = length . takeWhile id . zipWith (==) s

suffixes :: [a] -&gt; [[a]]
suffixes = tail . tails