الگوریتم KMP (کنوت–موریس–پرات)

تطبیق رشته در O(n + m): هیچ نویسه‌ای از متن دوباره خوانده نمی‌شود؛ بعد از ناهمخوانی، تابع پیشوند می‌گوید الگو چقدر جلو برود.

روش ساده بعد از ناهمخوانی الگو را فقط یک خانه جلو می‌برد و دوباره از اول مقایسه می‌کند. ولی ما از قبل می‌دانیم q نویسه‌ی آخر متن با P[0..q−1] برابر بوده‌اند. پس:

ادامه‌ی توضیح ↓

زمان: O(n + m)
حافظه: O(m)
CLRS، بخش ۳۲.۴
هوروویتز–ساهنی، فصل ۲

ورودی:

T="bacbabababab…" · P="ababa"خروجی PDF

الگوی ababa در bacbababababa سه بار پیدا می‌شود، در جابه‌جایی‌های ۴، ۶ و ۸؛ بعد از رخداد اول، KMP هم‌پوشانی را نگه می‌دارد و از اول شروع نمی‌کند.

def kmp_match(T, P):
n, m = len(T), len(P)
pi = prefix_function(P)
matches = []
q = 0 # how many characters of P match the text ending here
shift = 0 # where P sits under T, for the picture
for i in range(n):
while q > 0 and P[q] != T[i]:
q = pi[q - 1]
if P[q] == T[i]:
q = q + 1
if q == m:
matches.append(i - m + 1)
q = pi[q - 1]
shift = i - q + 1
return matches
def prefix_function(P):
pi = [0] * len(P)
k = 0
for q in range(1, len(P)):
while k > 0 and P[k] != P[q]:
k = pi[k - 1]
if P[k] == P[q]:
k = k + 1
pi[q] = k
return pi

ناوردا: بعد از هر گام، P[0..q−1] بلندترین پیشوندی از P است که با انتهای T[0..i] برابر است.

شروع اجرا

0123456789101112

bacbababababa

ababa

pi—

matches—

متغیرهای محلی

T'bacbababababa'

P'ababa'

نارنجی = در همین گام عوض شد

Call stack

kmp_match()خط 1

گام ۱ از ۱۱۵

توضیح

ایده

اگر T[i] با P[q] بخواند، q یکی زیاد می‌شود.
اگر نخواند، q را به π[q − 1] (بلندترین مرزِ قسمت جورشده) برمی‌گردانیم و دوباره امتحان می‌کنیم؛ متن دوباره خوانده نمی‌شود.
اگر q = m شد، الگو پیدا شده؛ با q = π[m − 1] ادامه می‌دهیم تا رخدادهای هم‌پوشان هم پیدا شوند.

هزینه

i فقط جلو می‌رود و هر برگشت q را کم می‌کند؛ پس کل کار O(n) به‌اضافه‌ی O(m) برای ساختن π.

در trace به چه چیزی نگاه کنی

اشاره‌گر i روی متن فقط جلو می‌رود؛ الگو زیر متن با جابه‌جایی فعلی کشیده شده و خانه‌های پررنگش جور شده‌اند.