🎯 Mục tiêu

• Hiểu ứng dụng tìm mẫu trong văn bản lớn (Rabin–Karp).
• Nhận dạng chuỗi tương tự trong kiểm tra chính tả hoặc AI text match.

📘 1️⃣ Thuật toán Rabin–Karp

Dùng Rolling Hash để so sánh hash của mẫu và mỗi đoạn văn bản dài |P|.

🌿 Python

BASE=257; MOD=10**9+9
def build_hash(s):
    n=len(s); pw=[1]*(n+1); h=[0]*(n+1)
    for i in range(1,n+1):
        pw[i]=pw[i-1]*BASE%MOD
        h[i]=(h[i-1]*BASE+ord(s[i-1]))%MOD
    return pw,h
def get_hash(l,r,pw,h):
    return (h[r]-h[l-1]*pw[r-l+1]%MOD+MOD)%MOD

text="hellotherehello"; pat="hello"
pw,h=build_hash(text)
hp=0
for c in pat: hp=(hp*BASE+ord(c))%MOD
for i in range(1,len(text)-len(pat)+2):
    if get_hash(i,i+len(pat)-1,pw,h)==hp:
        print("Match at",i-1)

🌿 C++

const long long BASE=257,MOD=1e9+9;
vector<long long> pw,h;
void build(string s){
    int n=s.size(); pw.assign(n+1,1);h.assign(n+1,0);
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*BASE%MOD;
        h[i]=(h[i-1]*BASE+s[i-1])%MOD;
    }
}
long long getH(int l,int r){
    return (h[r]-h[l-1]*pw[r-l+1]%MOD+MOD)%MOD;
}

📗 2️⃣ Ứng dụng thực tế

• Phát hiện đoạn văn sao chép (plagiarism check).
• Tự động gợi ý chính tả – so khớp với từ điển.
• Phân loại chuỗi trong xử lý ngôn ngữ tự nhiên (NLP).

🧩 Bài tập

1. Tìm tất cả vị trí P trong T bằng Rabin–Karp.
2. Kiểm tra 2 văn bản có giống nhau khi bỏ dấu chấm và khoảng trắng không.
3. Viết chương trình tự động phát hiện từ viết sai 1 ký tự (bằng so sánh hash gần đúng).

# So sánh hash khi bỏ qua 1 vị trí
# hoặc tính rolling hash cho từng từ rồi so sánh khoảng cách Levenshtein