Safe Haskell	None
Language	GHC2021

Data.RollingHash

Synopsis

newtype RollingHash (b :: Nat) = RollingHash {
- getRollingHash :: Int
}
data RollingHashTable (b :: Nat) = RollingHashTable {
- originalRH :: !(Vector Char)
- hashForwardRH :: !(Vector (RollingHash b))
- hashReverseRH :: !(Vector (RollingHash b))
- powCacheRH :: !(Vector (RollingHash b))
- recipPowCacheRH :: !(Vector (RollingHash b))
}
buildRollingHashTable :: forall (b :: Nat). KnownNat b => Vector Char -> RollingHashTable b
rollingHashTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b
rollingHashFromTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> RollingHash b
rollingHashReverseTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b
rollingHashReverseFromTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> RollingHash b
isPalindromeFromTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> Bool
appendRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b -> Int -> RollingHash b -> RollingHash b
longestCommonPrefixRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> Int
compareSuffixRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> Ordering
findSubstringIndexRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b -> Maybe Int
findSubstringIndicesRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b -> Vector Int
asRollingHashOf :: forall (b :: Nat). RollingHash b -> Proxy b -> RollingHash b
emptyRH :: forall (b :: Nat). RollingHash b
singletonRH :: forall (b :: Nat). Int -> RollingHash b
snocRH :: forall (b :: Nat). KnownNat b => RollingHash b -> Char -> RollingHash b
isPrimitiveRootRH :: Int -> Bool
genPrimitiveRootRH :: RandomGen g => g -> Int
withPrimitiveRootRH :: RandomGen g => g -> (forall (b :: Nat). KnownNat b => Proxy b -> a) -> a

Documentation

newtype RollingHash (b :: Nat) Source #

modulo 2^61-1

b should be a primitive root of 2^61-1

Constructors

RollingHash
Fields getRollingHash :: Int

Instances

Instances details

Vector Vector (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods basicUnsafeFreeze :: Mutable Vector s (RollingHash b) -> ST s (Vector (RollingHash b)) basicUnsafeThaw :: Vector (RollingHash b) -> ST s (Mutable Vector s (RollingHash b)) basicLength :: Vector (RollingHash b) -> Int basicUnsafeSlice :: Int -> Int -> Vector (RollingHash b) -> Vector (RollingHash b) basicUnsafeIndexM :: Vector (RollingHash b) -> Int -> Box (RollingHash b) basicUnsafeCopy :: Mutable Vector s (RollingHash b) -> Vector (RollingHash b) -> ST s () elemseq :: Vector (RollingHash b) -> RollingHash b -> b0 -> b0
MVector MVector (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods basicLength :: MVector s (RollingHash b) -> Int basicUnsafeSlice :: Int -> Int -> MVector s (RollingHash b) -> MVector s (RollingHash b) basicOverlaps :: MVector s (RollingHash b) -> MVector s (RollingHash b) -> Bool basicUnsafeNew :: Int -> ST s (MVector s (RollingHash b)) basicInitialize :: MVector s (RollingHash b) -> ST s () basicUnsafeReplicate :: Int -> RollingHash b -> ST s (MVector s (RollingHash b)) basicUnsafeRead :: MVector s (RollingHash b) -> Int -> ST s (RollingHash b) basicUnsafeWrite :: MVector s (RollingHash b) -> Int -> RollingHash b -> ST s () basicClear :: MVector s (RollingHash b) -> ST s () basicSet :: MVector s (RollingHash b) -> RollingHash b -> ST s () basicUnsafeCopy :: MVector s (RollingHash b) -> MVector s (RollingHash b) -> ST s () basicUnsafeMove :: MVector s (RollingHash b) -> MVector s (RollingHash b) -> ST s () basicUnsafeGrow :: MVector s (RollingHash b) -> Int -> ST s (MVector s (RollingHash b))
KnownNat b => IsString (RollingHash b) Source #	`>>>` `fromString @(RollingHash 2047) "abc"`406650978 `>>>` `fromString @(RollingHash 2047) "cba"`415031394 `>>>` `fromString @(RollingHash 100) "abc"`979899
Instance details Defined in Data.RollingHash Methods fromString :: String -> RollingHash b #
Num (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods (+) :: RollingHash b -> RollingHash b -> RollingHash b # (-) :: RollingHash b -> RollingHash b -> RollingHash b # (*) :: RollingHash b -> RollingHash b -> RollingHash b # negate :: RollingHash b -> RollingHash b # abs :: RollingHash b -> RollingHash b # signum :: RollingHash b -> RollingHash b # fromInteger :: Integer -> RollingHash b #
KnownNat b => Fractional (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods (/) :: RollingHash b -> RollingHash b -> RollingHash b # recip :: RollingHash b -> RollingHash b # fromRational :: Rational -> RollingHash b #
Show (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods showsPrec :: Int -> RollingHash b -> ShowS # show :: RollingHash b -> String # showList :: [RollingHash b] -> ShowS #
Eq (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods (==) :: RollingHash b -> RollingHash b -> Bool # (/=) :: RollingHash b -> RollingHash b -> Bool #
Ord (RollingHash b) Source #
Instance details Defined in Data.RollingHash Methods compare :: RollingHash b -> RollingHash b -> Ordering # (<) :: RollingHash b -> RollingHash b -> Bool # (<=) :: RollingHash b -> RollingHash b -> Bool # (>) :: RollingHash b -> RollingHash b -> Bool # (>=) :: RollingHash b -> RollingHash b -> Bool # max :: RollingHash b -> RollingHash b -> RollingHash b # min :: RollingHash b -> RollingHash b -> RollingHash b #
Unbox (RollingHash b) Source #
Instance details Defined in Data.RollingHash
newtype MVector s (RollingHash b) Source #
Instance details Defined in Data.RollingHash newtype MVector s (RollingHash b) = MV_RollingHash (MVector s Int)
newtype Vector (RollingHash b) Source #
Instance details Defined in Data.RollingHash newtype Vector (RollingHash b) = V_RollingHash (Vector Int)

data RollingHashTable (b :: Nat) Source #

Constructors

RollingHashTable
Fields originalRH :: !(Vector Char) hashForwardRH :: !(Vector (RollingHash b)) hashReverseRH :: !(Vector (RollingHash b)) powCacheRH :: !(Vector (RollingHash b)) recipPowCacheRH :: !(Vector (RollingHash b))

buildRollingHashTable :: forall (b :: Nat). KnownNat b => Vector Char -> RollingHashTable b Source #

rollingHashTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b Source #

>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashTo rht 3
406650978
>>> fromString @(RollingHash 2047) "abc"
406650978

rollingHashFromTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> RollingHash b Source #

>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashFromTo rht 1 4
410843235
>>> fromString @(RollingHash 2047) "bcd"
410843235

rollingHashReverseTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b Source #

>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashReverseTo rht 3
415031394
>>> fromString @(RollingHash 2047) "cba"
415031394

rollingHashReverseFromTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> RollingHash b Source #

>>> rht = buildRollingHashTable @2047 $ U.fromList "abcdef"
>>> rollingHashReverseFromTo rht 1 4
419223651
>>> fromString @(RollingHash 2047) "dcb"
419223651

isPalindromeFromTo :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> Bool Source #

O(1)

>>> rht = buildRollingHashTable @2047 $ U.fromList "mississippi"
>>> isPalindromeFromTo rht 0 11
False
>>> isPalindromeFromTo rht 1 5
True
>>> isPalindromeFromTo rht 1 8
True
>>> isPalindromeFromTo rht 0 0
True
>>> isPalindromeFromTo rht 11 11
True

appendRH Source #

Arguments

:: forall (b :: Nat). KnownNat b
=> RollingHashTable b
-> Int	length
-> RollingHash b
-> Int	length
-> RollingHash b
-> RollingHash b

>>> cacheSize = 10
>>> rht = buildRollingHashTable @2047 $ U.replicate cacheSize 'x'
>>> ab = "ab"
>>> cde = "cde"
>>> appendRH rht (length ab) (fromString ab) (length cde) (fromString cde)
1703952588079203
>>> fromString @(RollingHash 2047) "abcde"
1703952588079203

>>> rht = buildRollingHashTable @2047 U.empty
>>> ab = "ab"
>>> cde = "cde"
>>> appendRH rht (length ab) (fromString ab) (length cde) (fromString cde)
1703952588079203
>>> fromString @(RollingHash 2047) "abcde"
1703952588079203

longestCommonPrefixRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> Int Source #

LCP(Longet Common Prefix) of s[i..n) and s[j..n)

O(log n)

>>> rht = buildRollingHashTable @2047 $ U.fromList "abcxxxabc"
>>> longestCommonPrefixRH rht 0 6
3
>>> longestCommonPrefixRH rht 0 0
9
>>> longestCommonPrefixRH rht 8 8
1
>>> longestCommonPrefixRH rht 0 1
0

compareSuffixRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> Int -> Ordering Source #

O(log n)

>>> import Data.List
>>> rht = buildRollingHashTable @2047 $ U.fromList "mississippi"
>>> sortBy (compareSuffixRH rht) [0..11]
[11,10,7,4,1,0,9,8,6,3,5,2]
>>> rht = buildRollingHashTable @2047 $ U.fromList "abracadabra"
>>> sortBy (compareSuffixRH rht) [0..11]
[11,10,7,0,3,5,8,1,4,6,9,2]
>>> rht = buildRollingHashTable @2047 $ U.fromList "ababab"
>>> sortBy (compareSuffixRH rht) [0..6]
[6,4,2,0,5,3,1]

findSubstringIndexRH Source #

Arguments

:: forall (b :: Nat). KnownNat b
=> RollingHashTable b
-> Int	length
-> RollingHash b
-> Maybe Int

Rabin–Karp

O(n)

>>> rht = buildRollingHashTable @2047 $ U.fromList "xxxabcxxx"
>>> abc = "abc"
>>> findSubstringIndexRH rht (length abc) (fromString abc)
Just 3
>>> zzz = "zzz"
>>> findSubstringIndexRH rht (length zzz) (fromString zzz)
Nothing

findSubstringIndicesRH :: forall (b :: Nat). KnownNat b => RollingHashTable b -> Int -> RollingHash b -> Vector Int Source #

Rabin–Karp

O(n)

>>> rht = buildRollingHashTable @2047 $ U.fromList "xxxabcxxx"
>>> abc = "abc"
>>> findSubstringIndicesRH rht (length abc) (fromString abc)
[3]
>>> xxx = "xxx"
>>> findSubstringIndicesRH rht (length xxx) (fromString xxx)
[0,6]
>>> zzz = "zzz"
>>> findSubstringIndicesRH rht (length zzz) (fromString zzz)
[]

asRollingHashOf :: forall (b :: Nat). RollingHash b -> Proxy b -> RollingHash b Source #

emptyRH :: forall (b :: Nat). RollingHash b Source #

singletonRH :: forall (b :: Nat). Int -> RollingHash b Source #

snocRH :: forall (b :: Nat). KnownNat b => RollingHash b -> Char -> RollingHash b Source #

>>> F.foldl' (snocRH @2047) emptyRH "abc"
406650978

isPrimitiveRootRH :: Int -> Bool Source #

check if g is a primitive root of 2^61-1.

>>> isPrimitiveRootRH 2047
True
>>> take 10 $ filter isPrimitiveRootRH [2..]
[37,43,55,69,74,86,110,123,133,138]

genPrimitiveRootRH :: RandomGen g => g -> Int Source #

Generate a primitive root of 2^61-1.

>>> genPrimitiveRootRH (mkStdGen 123)
1600615663002506808
>>> isPrimitiveRootRH 1600615663002506808
True

withPrimitiveRootRH :: RandomGen g => g -> (forall (b :: Nat). KnownNat b => Proxy b -> a) -> a Source #

>>> withPrimitiveRootRH (mkStdGen 123) $ \proxy -> getRollingHash $ 456 `asRollingHashOf` proxy
456