Find pattern in text
Problem Introduction
In this problem, your goal is to implement the Rabin–Karp’s algorithm.
Problem Description
Task. In this problem your goal is to implement the Rabin–Karp’s algorithm for searching the given pattern
in the given text.
Input Format. There are two strings in the input: the pattern 𝑃 and the text 𝑇.
Constraints. 1 ≤ |𝑃| ≤ |𝑇| ≤ 5 · 105
. The total length of all occurrences of 𝑃 in 𝑇 doesn’t exceed 108
. The
pattern and the text contain only latin letters.
Output Format. Print all the positions of the occurrences of 𝑃 in 𝑇 in the ascending order. Use 0-based
indexing of positions in the the text 𝑇.
Time Limits. C: 1 sec, C++: 1 sec, Java: 5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3
sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit. 512MB.
Sample 1.
Input:
aba
abacaba
Output:
0 4
Explanation:
The pattern 𝑎𝑏𝑎 can be found in positions 0 (abacaba) and 4 (abacaba) of the text 𝑎𝑏𝑎𝑐𝑎𝑏𝑎.
Sample 2.
Input:
Test
testTesttesT
Output:
4
Explanation:
Pattern and text are case-sensitive in this problem. Pattern 𝑇 𝑒𝑠𝑡 can only be found in position 4 in
the text 𝑡𝑒𝑠𝑡𝑇 𝑒𝑠𝑡𝑡𝑒𝑠𝑇.
Sample 3.
Input:
aaaaa
baaaaaaa
Output:
1 2 3
Note that the occurrences of the pattern in the text can be overlapping, and that’s ok, you still need
to output all of them.Find Substring Solution :
class TextSearch:
def __init__(self, pattern, text):
self._pattern = pattern
self._text = text
self._window = len(pattern)
self._scan_bound = len(text) - len(pattern) + 1
self._checksums = []
def checksum(self, string):
return sum([ord(string[i]) for i in range(len(string))])
def precompute_hashes(self):
self._checksums = [self.checksum(self._text[:self._window])]
for i in range(1, self._scan_bound):
old_hash = self._checksums[i - 1]
left_l_hash = ord(self._text[i - 1])
right_l_hash = ord(self._text[i + self._window - 1])
ith_hash = old_hash - left_l_hash + right_l_hash
self._checksums.append(ith_hash)
def find(self):
pattern_checksum = self.checksum(self._pattern)
self.precompute_hashes()
results = []
for i in range(self._scan_bound):
if pattern_checksum == self._checksums[i]:
if self._pattern == self._text[i:i + self._window]:
results.append(i)
return results
if __name__ == "__main__":
pattern, text = input().rstrip(), input().rstrip()
ts = TextSearch(pattern, text)
result = ts.find()
print(" ".join(map(str, result)))