Rabin-Karp Algorithm for substring search. Parameters: text (str): The main text where the pattern is to be searched. pattern (str): The pattern to search for. base (int): The base used for hashing (default: 256). prime (int): A prime number used to reduce hash v
(text, pattern, base=256, prime=101)
| 1 | def rabin_karp(text, pattern, base=256, prime=101): |
| 2 | """ |
| 3 | Rabin-Karp Algorithm for substring search. |
| 4 | |
| 5 | Parameters: |
| 6 | text (str): The main text where the pattern is to be searched. |
| 7 | pattern (str): The pattern to search for. |
| 8 | base (int): The base used for hashing (default: 256). |
| 9 | prime (int): A prime number used to reduce hash values (default: 101). |
| 10 | |
| 11 | Returns: |
| 12 | list: Starting indices of all occurrences of the pattern in the text. |
| 13 | """ |
| 14 | n, m = len(text), len(pattern) |
| 15 | if m > n: |
| 16 | return [] |
| 17 | |
| 18 | pattern_hash = 0 # Hash value for pattern |
| 19 | text_hash = 0 # Hash value for current window in text |
| 20 | h = 1 # The value of base^(m-1) |
| 21 | |
| 22 | # Compute h = (base^(m-1)) % prime |
| 23 | for _ in range(m - 1): |
| 24 | h = (h * base) % prime |
| 25 | |
| 26 | # Compute initial hash values for pattern and first window of text |
| 27 | for i in range(m): |
| 28 | pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime |
| 29 | text_hash = (base * text_hash + ord(text[i])) % prime |
| 30 | |
| 31 | # List to store starting indices of pattern matches |
| 32 | result = [] |
| 33 | |
| 34 | # Slide the pattern over text one character at a time |
| 35 | for i in range(n - m + 1): |
| 36 | # Check if the hash values match |
| 37 | if pattern_hash == text_hash: |
| 38 | # If hash matches, check characters one by one for a real match |
| 39 | if text[i:i + m] == pattern: |
| 40 | result.append(i) |
| 41 | |
| 42 | # Compute hash for next window of text |
| 43 | if i < n - m: |
| 44 | text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime |
| 45 | |
| 46 | # Make sure text_hash is positive |
| 47 | if text_hash < 0: |
| 48 | text_hash += prime |
| 49 | |
| 50 | return result |
| 51 | |
| 52 | |
| 53 | # Example Usage |