Package gw.internal.gosu.util
Class RabinKarpHash
java.lang.Object
gw.internal.gosu.util.RabinKarpHash
Fast multi-pattern string matcher.
Quick and dirty implementation of Rabin-Karp algorithm. Used for paths matching.
We mach patterns from the end to reduce amount of possible collisions (filesystem paths tend to have common prefixes,
like package names, etc).
FIXME: Tests...
- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final int
private final int
private String[]
private static final int
private static int[]
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
exactMatch
(String str, int i) Check for exact match.boolean
private static int
Find the shortest of all patterns.private int
reverseHash
(String str) Take rolling hash of last 'block' characters.private int
Update rolling hash values.
-
Field Details
-
A
private static final int A- See Also:
-
_block
private final int _block -
_Apowblock
private final int _Apowblock -
_hashes
-
_patterns
-
CHAR_HASHES
private static int[] CHAR_HASHES
-
-
Constructor Details
-
RabinKarpHash
-
-
Method Details
-
minLen
Find the shortest of all patterns.- Parameters:
patterns
-- Returns:
-
matches
-
exactMatch
Check for exact match. FIXME:- Parameters:
str
-i
-- Returns:
-
rollHash
Update rolling hash values.- Parameters:
hashvalue
-str
-i
-- Returns:
-
reverseHash
Take rolling hash of last 'block' characters. Start from the end of the string.- Parameters:
str
-- Returns:
-