Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.RollingHash

Description

The rolling hash algorithm lets you create ( \(O(N)\) or \(O(N \log N)\) ) fastly ( \(O(1)\) ) comparable, concatanatable string slices.

Overview

Rolling hash of a string is calculated as a B-adic number. As an example, slice [2, 4] of a string "abcde" is given as this:

           s :=     a       b       c       d       e
           s4 = b^4 a + b^3 b + b^2 c + b^1 d + b^0 e
           s2 = b^1 a + b^0 b
s4 - s2 * b^3 =                 b^2 c + b^1 d + b^0 e

Cumulative sum-based implementation

Unless extreamly fast calculaton is required, RH is better.

RollingHash is a cumulative sum-based implementation. It needs to calculate \(b^{n_1} / b^{n_2}\) for the inverse operation. Thus it holds a cache of \(\{b^{n}\}_{n}\) and not so flexible.

Monoid-based implmentation

RH is the monoid-based rolling hash implementation. Convert a string into a segment tree of RH and you win.

Synopsis

data RH b p = RH {
- nextDigitRH :: !Int
- hashRH :: !Int
}
rh1 :: forall b p. KnownNat b => Int -> RH b p
type RHRepr = A2 Int
data RollingHash b p = RollingHash {
- sourceLength :: !Int
- dimensions :: !(Vector Int)
- hashSum :: !(Vector Int)
}
type HashInt = 100 :: Nat
newRH :: forall p. KnownNat p => String -> RollingHash HashInt p
lengthRH :: RollingHash b p -> Int
data HashSlice p = HashSlice {
- hashValue :: !Int
- hashLength :: !Int
}
sliceRH :: forall b p. KnownNat p => RollingHash b p -> Int -> Int -> HashSlice p
consHS :: forall b p. KnownNat p => RollingHash b p -> HashSlice p -> HashSlice p -> HashSlice p
emptyHS :: HashSlice p
concatHS :: forall b p t. (KnownNat p, Foldable t) => RollingHash b p -> t (HashSlice p) -> HashSlice p

Documentation

data RH b p #

Rolling hash monoid. Essensially a (Dual) Affine2d ModInt.

Typical prolbems

ABC 331 F - Palindrome Query

Constructors

RH
Fields nextDigitRH :: !Int \(b^{length}\). hashRH :: !Int The hash value.

Instances

Instances details

Vector Vector (RH b p) #
Instance details Defined in Data.RollingHash Methods basicUnsafeFreeze :: Mutable Vector s (RH b p) -> ST s (Vector (RH b p)) # basicUnsafeThaw :: Vector (RH b p) -> ST s (Mutable Vector s (RH b p)) # basicLength :: Vector (RH b p) -> Int # basicUnsafeSlice :: Int -> Int -> Vector (RH b p) -> Vector (RH b p) # basicUnsafeIndexM :: Vector (RH b p) -> Int -> Box (RH b p) # basicUnsafeCopy :: Mutable Vector s (RH b p) -> Vector (RH b p) -> ST s () # elemseq :: Vector (RH b p) -> RH b p -> b0 -> b0 #
MVector MVector (RH b p) #
Instance details Defined in Data.RollingHash Methods basicLength :: MVector s (RH b p) -> Int # basicUnsafeSlice :: Int -> Int -> MVector s (RH b p) -> MVector s (RH b p) # basicOverlaps :: MVector s (RH b p) -> MVector s (RH b p) -> Bool # basicUnsafeNew :: Int -> ST s (MVector s (RH b p)) # basicInitialize :: MVector s (RH b p) -> ST s () # basicUnsafeReplicate :: Int -> RH b p -> ST s (MVector s (RH b p)) # basicUnsafeRead :: MVector s (RH b p) -> Int -> ST s (RH b p) # basicUnsafeWrite :: MVector s (RH b p) -> Int -> RH b p -> ST s () # basicClear :: MVector s (RH b p) -> ST s () # basicSet :: MVector s (RH b p) -> RH b p -> ST s () # basicUnsafeCopy :: MVector s (RH b p) -> MVector s (RH b p) -> ST s () # basicUnsafeMove :: MVector s (RH b p) -> MVector s (RH b p) -> ST s () # basicUnsafeGrow :: MVector s (RH b p) -> Int -> ST s (MVector s (RH b p)) #
(KnownNat b, KnownNat p) => Monoid (RH b p) #
Instance details Defined in Data.RollingHash Methods mempty :: RH b p # mappend :: RH b p -> RH b p -> RH b p # mconcat :: [RH b p] -> RH b p #
(KnownNat b, KnownNat p) => Semigroup (RH b p) #
Instance details Defined in Data.RollingHash Methods (<>) :: RH b p -> RH b p -> RH b p # sconcat :: NonEmpty (RH b p) -> RH b p # stimes :: Integral b0 => b0 -> RH b p -> RH b p #
Show (RH b p) #
Instance details Defined in Data.RollingHash Methods showsPrec :: Int -> RH b p -> ShowS # show :: RH b p -> String # showList :: [RH b p] -> ShowS #
Eq (RH b p) #
Instance details Defined in Data.RollingHash Methods (==) :: RH b p -> RH b p -> Bool # (/=) :: RH b p -> RH b p -> Bool #
Ord (RH b p) #
Instance details Defined in Data.RollingHash Methods compare :: RH b p -> RH b p -> Ordering # (<) :: RH b p -> RH b p -> Bool # (<=) :: RH b p -> RH b p -> Bool # (>) :: RH b p -> RH b p -> Bool # (>=) :: RH b p -> RH b p -> Bool # max :: RH b p -> RH b p -> RH b p # min :: RH b p -> RH b p -> RH b p #
Unbox (RH b p) #
Instance details Defined in Data.RollingHash
IsoUnbox (RH b p) RHRepr #
Instance details Defined in Data.RollingHash Methods toURepr :: RH b p -> RHRepr # fromURepr :: RHRepr -> RH b p #
newtype MVector s (RH b p) #
Instance details Defined in Data.RollingHash newtype MVector s (RH b p) = MV_RH (MVector s RHRepr)
newtype Vector (RH b p) #
Instance details Defined in Data.RollingHash newtype Vector (RH b p) = V_RH (Vector RHRepr)

rh1 :: forall b p. KnownNat b => Int -> RH b p #

\(O(1)\) Creates a one-length RH from an integer.

Warning

The input must be less than p.

type RHRepr = A2 Int #

data RollingHash b p #

Rolling hash of a string.

Internals

Slice (2, 4) of "abcdef" is given as this:

           s :=     a       b       c       d       e
           s4 = b^4 a + b^3 b + b^2 c + b^1 d + b^0 e
           s2 = b^1 a + b^0 b
s4 - s2 * b^3 =                 b^2 c + b^1 d + b^0 e

Constructors

RollingHash
Fields sourceLength :: !Int dimensions :: !(Vector Int) \(\{B^i mod p\}_{i \elem [0, n)}\) hashSum :: !(Vector Int)

Instances

Instances details

Show (RollingHash b p) #
Instance details Defined in Data.RollingHash Methods showsPrec :: Int -> RollingHash b p -> ShowS # show :: RollingHash b p -> String # showList :: [RollingHash b p] -> ShowS #
Eq (RollingHash b p) #
Instance details Defined in Data.RollingHash Methods (==) :: RollingHash b p -> RollingHash b p -> Bool # (/=) :: RollingHash b p -> RollingHash b p -> Bool #

type HashInt = 100 :: Nat #

Type level integer that represents the B-adic number used for the rolling hash algorithm.

newRH :: forall p. KnownNat p => String -> RollingHash HashInt p #

\(O(N)\) Creates a rolling hash of given string.

lengthRH :: RollingHash b p -> Int #

\(O(1)\) Retrieves the original length of the RollingHash string.

data HashSlice p #

HashSlice value length. See also the example of RollingHash.

Constructors

HashSlice
Fields hashValue :: !Int hashLength :: !Int

Instances

Instances details

Show (HashSlice p) #
Instance details Defined in Data.RollingHash Methods showsPrec :: Int -> HashSlice p -> ShowS # show :: HashSlice p -> String # showList :: [HashSlice p] -> ShowS #
Eq (HashSlice p) #
Instance details Defined in Data.RollingHash Methods (==) :: HashSlice p -> HashSlice p -> Bool # (/=) :: HashSlice p -> HashSlice p -> Bool #

sliceRH :: forall b p. KnownNat p => RollingHash b p -> Int -> Int -> HashSlice p #

\(O(1)\) Slices a rolling hash string.

consHS :: forall b p. KnownNat p => RollingHash b p -> HashSlice p -> HashSlice p -> HashSlice p #

\(O(1)\) Cons two rolling hash slices.

emptyHS :: HashSlice p #

\(O(1)\) Creates an empty rolling hash slice.

concatHS :: forall b p t. (KnownNat p, Foldable t) => RollingHash b p -> t (HashSlice p) -> HashSlice p #

\(O(K)\) Concatanates two rolling hash slices.