Rabin-Karp Algorithm — Rolling Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

def rabin_karp_multi_pattern(text: str, patterns: list[str]) -> dict[str, list[int]]:
    """
    Find all occurrences of multiple patterns in text.
    
    Assumes all patterns have the same length.
    Returns dict mapping each pattern to list of match positions.
    
    Time: O(n + km) expected where k = number of patterns
    Space: O(k) for pattern hash storage
    """
    if not patterns:
        return {}
    
    n = len(text)
    m = len(patterns[0])  # Assumes equal-length patterns
    
    # Validate all patterns have same length
    if not all(len(p) == m for p in patterns):
        raise ValueError("All patterns must have the same length")
    
    if m > n:
        return {p: [] for p in patterns}
    
    base = 31
    mod = 10**9 + 7
    
    # Preprocessing: compute all pattern hashes
    pattern_hashes = {}  # hash -> list of patterns with that hash
    for pattern in patterns:
        h = 0
        for c in pattern:
            h = (h * base + ord(c)) % mod
        
        # Multiple patterns might have same hash (collision)
        if h not in pattern_hashes:
            pattern_hashes[h] = []
        pattern_hashes[h].append(pattern)
    
    # Initialize result
    results = {p: [] for p in patterns}
    
    # Compute first window hash
    window_hash = 0
    for i in range(m):
        window_hash = (window_hash * base + ord(text[i])) % mod
    
    # Precompute base^(m-1)
    base_power = pow(base, m - 1, mod)
    
    # Scan text once
    for i in range(n - m + 1):
        # O(1) hash set lookup
        if window_hash in pattern_hashes:
            # Verify against all patterns with this hash
            window_text = text[i:i+m]
            for pattern in pattern_hashes[window_hash]:
                if window_text == pattern:
                    results[pattern].append(i)
        
        # Roll hash
        if i < n - m:
            outgoing = ord(text[i])
            incoming = ord(text[i + m])
            window_hash = ((window_hash - outgoing * base_power) * base + incoming) % mod
            if window_hash < 0:
                window_hash += mod
    
    return results
 
 
# Example usage
text = "ABABCABABCABABCAB"
patterns = ["ABABC", "BABCA", "ABCAB", "CABAB"]
 
results = rabin_karp_multi_pattern(text, patterns)
for pattern, positions in results.items():
    if positions:
        print(f"'{pattern}' found at positions: {positions}")
    else:
        print(f"'{pattern}' not found")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

from collections import defaultdict
 
def rabin_karp_variable_length(text: str, patterns: list[str]) -> dict[str, list[int]]:
    """
    Multi-pattern Rabin-Karp supporting variable-length patterns.
    
    Groups patterns by length and runs separate searches per group.
    Efficient when number of distinct lengths is small.
    """
    if not patterns:
        return {}
    
    n = len(text)
    base = 31
    mod = 10**9 + 7
    
    # Group patterns by length
    by_length = defaultdict(list)
    for pattern in patterns:
        by_length[len(pattern)].append(pattern)
    
    results = {p: [] for p in patterns}
    
    for m, patterns_of_length in by_length.items():
        if m > n:
            continue
        
        # Build hash set for this length
        pattern_hashes = defaultdict(list)
        for pattern in patterns_of_length:
            h = 0
            for c in pattern:
                h = (h * base + ord(c)) % mod
            pattern_hashes[h].append(pattern)
        
        # Compute first window hash
        window_hash = 0
        for i in range(m):
            window_hash = (window_hash * base + ord(text[i])) % mod
        
        base_power = pow(base, m - 1, mod)
        
        # Scan text for this length
        for i in range(n - m + 1):
            if window_hash in pattern_hashes:
                window_text = text[i:i+m]
                for pattern in pattern_hashes[window_hash]:
                    if window_text == pattern:
                        results[pattern].append(i)
            
            if i < n - m:
                outgoing = ord(text[i])
                incoming = ord(text[i + m])
                window_hash = ((window_hash - outgoing * base_power) * base + incoming) % mod
                if window_hash < 0:
                    window_hash += mod
    
    return results
 
 
# Example with variable-length patterns
text = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG"
patterns = ["THE", "QUICK", "BROWN FOX", "LAZY"]
 
results = rabin_karp_variable_length(text, patterns)
for pattern, positions in results.items():
    if positions:
        print(f"'{pattern}' found at positions: {positions}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

def plagiarism_detection(target: str, corpus: list[str], n: int = 5) -> dict:
    """
    Detect potential plagiarism by finding shared n-grams.
    
    Args:
        target: Document to check for plagiarism
        corpus: List of reference documents
        n: Size of word n-grams to use
    
    Returns:
        Dict with plagiarism analysis for each corpus document
    """
    # Extract word n-grams from target
    target_words = target.split()
    if len(target_words) < n:
        return {}
    
    # Create n-gram patterns
    ngrams = set()
    for i in range(len(target_words) - n + 1):
        ngram = ' '.join(target_words[i:i+n])
        ngrams.add(ngram)
    
    # For equal-length search, group by length
    # Here we simplify by assuming space-separated words
    results = {}
    
    for doc_id, doc in enumerate(corpus):
        doc_name = f"Document {doc_id}"
        
        # Find matches using Rabin-Karp
        matches = rabin_karp_variable_length(doc, list(ngrams))
        
        match_count = sum(len(positions) for positions in matches.values())
        match_ratio = match_count / max(1, len(doc.split()) - n + 1)
        
        results[doc_name] = {
            'match_count': match_count,
            'match_ratio': match_ratio,
            'plagiarism_flag': match_ratio > 0.1,  # 10% threshold
            'matched_ngrams': [ng for ng, pos in matches.items() if pos]
        }
    
    return results
 
 
# Example usage
target = "The quick brown fox jumps over the lazy dog"
corpus = [
    "The quick brown fox runs through the forest",
    "This is a completely different document about cats",
    "The quick brown fox jumps over the lazy sleeping dog"
]
 
analysis = plagiarism_detection(target, corpus, n=3)
for doc, info in analysis.items():
    print(f"{doc}: {info['match_count']} matches, " +
          f"ratio={info['match_ratio']:.2%}, " +
          f"flagged={info['plagiarism_flag']}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

from collections import defaultdict
from dataclasses import dataclass
from typing import Iterator
 
@dataclass
class Match:
    """Represents a pattern match in text."""
    pattern: str
    position: int
    length: int
    
    def __repr__(self):
        return f"Match('{self.pattern}' at {self.position})"
 
 
class MultiPatternMatcher:
    """
    Production-ready multi-pattern matching using Rabin-Karp.
    
    Features:
    - Supports patterns of varying lengths
    - Double hashing for collision resistance
    - Streaming-capable design
    - Match count and position tracking
    """
    
    def __init__(self, patterns: list[str], 
                 base1: int = 31, mod1: int = 10**9 + 7,
                 base2: int = 37, mod2: int = 10**9 + 9):
        if not patterns:
            raise ValueError("At least one pattern required")
        
        self.patterns = list(set(patterns))  # Deduplicate
        self.base1, self.mod1 = base1, mod1
        self.base2, self.mod2 = base2, mod2
        
        # Group patterns by length
        self.by_length: dict[int, dict[tuple, list[str]]] = defaultdict(dict)
        
        for pattern in self.patterns:
            m = len(pattern)
            h1 = self._hash(pattern, base1, mod1)
            h2 = self._hash(pattern, base2, mod2)
            key = (h1, h2)
            
            if key not in self.by_length[m]:
                self.by_length[m][key] = []
            self.by_length[m][key].append(pattern)
        
        self.lengths = sorted(self.by_length.keys())
    
    def _hash(self, s: str, base: int, mod: int) -> int:
        """Compute polynomial hash of string."""
        h = 0
        for c in s:
            h = (h * base + ord(c)) % mod
        return h
    
    def search(self, text: str) -> list[Match]:
        """Find all pattern occurrences in text."""
        return list(self.search_iter(text))
    
    def search_iter(self, text: str) -> Iterator[Match]:
        """Iterate over pattern occurrences (memory-efficient)."""
        n = len(text)
        
        for m in self.lengths:
            if m > n:
                continue
            
            patterns_at_length = self.by_length[m]
            
            # Compute initial window hashes
            h1 = self._hash(text[:m], self.base1, self.mod1)
            h2 = self._hash(text[:m], self.base2, self.mod2)
            
            # Base powers for rolling
            bp1 = pow(self.base1, m - 1, self.mod1)
            bp2 = pow(self.base2, m - 1, self.mod2)
            
            for i in range(n - m + 1):
                key = (h1, h2)
                
                if key in patterns_at_length:
                    window = text[i:i+m]
                    for pattern in patterns_at_length[key]:
                        if window == pattern:
                            yield Match(pattern, i, m)
                
                # Roll hashes
                if i < n - m:
                    out = ord(text[i])
                    inp = ord(text[i + m])
                    
                    h1 = ((h1 - out * bp1) * self.base1 + inp) % self.mod1
                    h2 = ((h2 - out * bp2) * self.base2 + inp) % self.mod2
                    
                    if h1 < 0: h1 += self.mod1
                    if h2 < 0: h2 += self.mod2
    
    def contains_any(self, text: str) -> bool:
        """Check if text contains any pattern (early termination)."""
        for _ in self.search_iter(text):
            return True
        return False
    
    def count_matches(self, text: str) -> dict[str, int]:
        """Count occurrences of each pattern."""
        counts = {p: 0 for p in self.patterns}
        for match in self.search_iter(text):
            counts[match.pattern] += 1
        return counts
 
 
# Example usage
matcher = MultiPatternMatcher([
    "hello",
    "world",
    "hell",
    "algorithm"
])
 
text = """
Hello, World! This is a test of the hello algorithm.
The world of algorithms is vast. Hello again!
"""
 
print("All matches:")
for match in matcher.search(text.lower()):
    print(f"  {match}")
 
print(f"
Contains any: {matcher.contains_any(text.lower())}")
print(f"
Match counts: {matcher.count_matches(text.lower())}")