KMP Algorithm (LPS Table and Linear Search) — KMP வழிமுறை

KMP — pattern முன் செயலாக்கம்; பொருந்தாதபோது எவ்வளவு நகர்த்துவது; LPS (proper prefix=suffix அதிகநீளம்) மையம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

DNA motif — பெரிய மரபணு O(n+m). IDE தேடல் — engine கலவை.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

lps[i] — pat[0:i+1] இன் proper prefix=suffix அதிகநீளம். பொருத்தம்: i உரை, j pattern; mismatch — j=lps[j-1]; j==0 என i++.

Pythonில் முயற்சி செய்வோம்

def compute_lps(pat: str) -> list[int]:
    m = len(pat)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps


print(compute_lps("ababac"))

அடிக்கடி நேரும் தவறுகள்

• j==m index.
• LPS மந்த O(m³) — நிலையான O(m) கட்டுமானம்.

முக்கியச் சுருக்கக் குறிப்புகள்

• முழு KMPக்கு முன் LPS கைவரைபு.
• Rabin–Karp ஒப்பீடு.