提出 #9534064

---

ソースコード 拡げる

import           Control.Monad
import qualified Control.Monad.ST            as ST
import           Data.Array.IO
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Maybe
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM

rollingHash :: BS.ByteString -> Int -> (V.Vector Word, V.Vector Word)
rollingHash s b = ST.runST $ do
  let sz = BS.length s
      b' = fromIntegral b
  h <- VM.new (sz+1)
  VM.write h 0 (0::Word)
  power <- VM.new (sz+1)
  VM.write power 0 (1::Word)
  forM_ [0..(sz-1)] $ \i -> do
    powi <- VM.read power i
    VM.write power (i+1) (powi * b')
    hi <- VM.read h i
    let si = fromIntegral $ ord $ BS.index s i
    VM.write h (i+1) (hi * b' + si)
  h' <- V.freeze h
  power' <- V.freeze power
  return (h', power')

getRH :: (V.Vector Word, V.Vector Word) -> Int -> Int -> Word
getRH (h, power) l r = hr - pr_1 * hl
  where hr = h V.! r
        pr_1 = power V.! (r-l)
        hl = h V.! l

bisectRight :: Ord a => (Int -> a) -> a -> Int -> Int -> Int
bisectRight f x lo hi
  | lo >= hi  = lo
  | x < f mid = bisectRight f x lo mid
  | otherwise = bisectRight f x (mid+1) hi
  where
    mid = lo + (hi - lo) `div` 2

readInt = fst . fromJust . BS.readInt
getInt = readInt <$> BS.getLine

check' i j f | i > j     = False
             | otherwise = f i || check' (i+1) j f

main = do
  n <- getInt
  s <- BS.getLine

  let rh1 = rollingHash s 100000007
      rh2 = rollingHash s 10007
      check k =
        check' 0 (n-2*k) $ \i ->
          let hi1 = getRH rh1 i (i+k)
              hi2 = getRH rh2 i (i+k)
              f = (\j -> (hi1 == getRH rh1 (i+k+j) (i+j+2*k) &&
                          hi2 == getRH rh2 (i+k+j) (i+j+2*k)))
          in
            check' 0 (n-i-2*k) f

      ans = bisectRight (not . check) False 0 (n `div` 2 + 1) - 1

  print ans

提出情報

ジャッジ結果