Belajar Algoritm - String Algorithms

#Pendahuluan

Setelah di episode 21 kita menutup FASE 5 dengan Network Flow, pada episode ini kita memulai FASE 6: APPLIED, RANDOMIZED & MODERN dengan String Algorithms — algoritma untuk pencarian pola (pattern matching) dalam teks. Brute force mencari pola dalam teks membutuhkan O(n × m), tetapi algoritma cerdas bisa mencapai O(n + m).

String algorithms bukan hanya akademis — mereka adalah fondasi untuk text search (grep, Elasticsearch), plagiarism detection (Moss), bioinformatics (DNA sequence matching), dan version control (diff algorithms). Memahami KMP, Rabin-Karp, dan Z-algorithm memberikan kalian alat yang powerful untuk masalah text processing.

#Knuth-Morris-Pratt (KMP)

KMP mencari semua kemunculan pola P dalam teks T dalam O(n + m). Kuncinya: saat karakter tidak cocok, KMP tidak mundur ke awal — ia menggunakan failure function (prefix function) untuk mengetahui posisi terbaik untuk melanjutkan.

#Failure Function (Prefix Function)

π[i] = panjang prefix terpanjang dari P[0..i] yang juga merupakan suffix.

def compute_failure(pattern):
    m = len(pattern)
    pi = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            pi[i] = length
            i += 1
        else:
            if length != 0:
                length = pi[length - 1]
            else:
                pi[i] = 0
                i += 1
    return pi

#Pattern Matching

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    pi = compute_failure(pattern)
    result = []
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
        if j == m:
            result.append(i - j)
            j = pi[j - 1]
        elif i < n and text[i] != pattern[j]:
            if j != 0:
                j = pi[j - 1]
            else:
                i += 1
    return result

Mengapa O(n + m)? Indeks i hanya bergerak maju (tidak pernah mundur). Jumlah operasi failure function = O(m). Total: O(n + m).

#Rabin-Karp

Rabin-Karp menggunakan rolling hash untuk membandingkan pola dengan substring teks. Hash memungkinkan perbandingan dalam O(1), sehingga pencarian menjadi O(n + m) average.

def rabin_karp(text, pattern, d=256, q=101):
    """d = jumlah karakter, q = modulus hash"""
    n, m = len(text), len(pattern)
    h = pow(d, m - 1, q)  # d^(m-1) mod q
    p_hash = 0  # hash pola
    t_hash = 0  # hash teks saat ini
    
    # Hitung hash awal
    for i in range(m):
        p_hash = (d * p_hash + ord(pattern[i])) % q
        t_hash = (d * t_hash + ord(text[i])) % q
    
    result = []
    for i in range(n - m + 1):
        if p_hash == t_hash:
            if text[i:i+m] == pattern:
                result.append(i)
        if i < n - m:
            t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
            if t_hash < 0:
                t_hash += q
    
    return result

Rolling hash: setelah hash window [i..i+m-1], hash window [i+1..i+m] dihitung dalam O(1) dengan menghapus kontribusi karakter lama dan menambah karakter baru.

#Z-Algorithm

Z-algorithm menghitung Z-array: Z[i] = panjang substring terpanjang yang dimulai dari posisi i yang juga merupakan prefix dari string.

def z_function(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i + 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z

Pattern matching dengan Z: buat string P + "$" + T (pola + karakter delimiter + teks), hitung Z-array. Jika Z[i] == m (panjang pola), maka ada kemunculan pola di posisi i - m - 1 dalam teks.

#Aplikasi

#Bioinformatics

DNA sequence alignment menggunakan string matching untuk menemukan pola dalam jutaan karakter DNA. KMP dan suffix array adalah fondasi tools seperti BLAST dan FASTA.

#Praktik

Implementasi KMP → cari semua kemunculan pola dalam teks besar. Bandingkan waktu dengan brute force. Verifikasi bahwa KMP selalu O(n + m) sementara brute force bisa mencapai O(n × m) pada kasus buruk.

#Penutup

Pada episode 22 ini, kalian telah memahami:

• KMP: O(n + m) dengan failure function — tidak pernah mundur.
• Rabin-Karp: O(n + m) average dengan rolling hash — cocok untuk multiple pattern.
• Z-algorithm: O(n) untuk prefix matching — elegan dan cepat.
• String algorithms adalah fondasi text search, plagiarism detection, dan bioinformatics.

Di episode 23 selanjutnya kita akan membahas Geometric Algorithms — convex hull (Graham scan, monotone chain), line segment intersection, dan closest pair. Sampai jumpa di episode 23!