Rabin-Karp algorithm in Python

rabin_karp.py

from fastcore.all import *


class Node:
    def __init__(self, val, start=-1, end=-1):
        store_attr()

    def print(self):
        print(f"{self.val}: index from {self.start} to {self.end}.")


def search(text, pattern, q=157):  # q is a prime number
    n = len(text)
    m = len(pattern)
    d = n
    p = 0
    t = 0
    h = 1
    result = L()

    for i in range(m - 1):
        h = (h * d) % q

    # Calculate hash value for pattern and text
    for i in range(m):
        p = (d * p + ord(pattern[i])) % q
        t = (d * t + ord(text[i])) % q

    # Find the match
    for i in range(n - m + 1):
        if p == t:
            match = True
            for j in range(m):
                if text[i + j] != pattern[j]:
                    match = False
                    break

            if match:
                currentNode = Node(pattern, start=i, end=i + m - 1)
                result.append(currentNode)

        if i < n - m:
            t = (d * (t - ord(text[i]) * h) + ord(text[i + m])) % q

            if t < 0:
                t += q

    return result


if __name__ == "__main__":
    text = "ABCCDDDAEFGCLEMONCDADLEM"
    patterns = "LEM"
    result = search(text, patterns)

    for node in result:
        node.print()


""" Result

LEM: index from 12 to 14.

LEM: index from 21 to 23.

"""