AlgoVerse

تابع پیشوند KMP

برای هر پیشوند الگو، طول بلندترین پیشوند سره‌ای را که پسوند آن هم هست حساب می‌کند؛ KMP با همین جدول بعد از ناهمخوانی می‌داند چقدر جلو برود.

مرز یک رشته، پیشوند سره‌ای است که پسوند آن هم هست (برای ababa: aba و a). π[q] طول بلندترین مرزِ P[0..q] است.

ادامه‌ی توضیح ↓
ورودی:
P="ababaca"خروجی PDF

الگوی ababaca؛ π = (0, 0, 1, 2, 3, 0, 1).

  1. def prefix_function(P):
  2. # pi[q] = the length of the longest proper prefix of P[0..q] that is also a suffix of it.
  3. m = len(P)
  4. pi = [0] * m
  5. table = [list(P), pi]
  6. k = 0
  7. for q in range(1, m):
  8. while k > 0 and P[k] != P[q]:
  9. k = pi[k - 1]
  10. if P[k] == P[q]:
  11. k = k + 1
  12. pi[q] = k
  13. return pi

ناوردا: قبل از دور q، عدد k برابر π[q − 1] است: P[0..k−1] بلندترین پیشوندی است که با انتهای P[0..q−1] برابر است.

شروع اجرا

0123456
ababaca

جدول هنوز خالی است.

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

P'ababaca'

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

Call stack

  1. prefix_function()خط 1
گام ۱ از ۳۹
خط سیاه = set_pi · خط نارنجی = گام کلیدیset_pi: 0/6 · extend: 0/4 · fall_back: 0/2
    توضیح

    ایده

    مرز یک رشته، پیشوند سره‌ای است که پسوند آن هم هست (برای ababa: aba و a). π[q] طول بلندترین مرزِ P[0..q] است.

    چرا مهم است؟

    در KMP وقتی q نویسه از الگو جور شده و نویسه‌ی بعدی نمی‌خواند، لازم نیست از اول شروع کنیم: بلندترین مرزِ قسمت جورشده دقیقاً همان مقداری است که هنوز معتبر است، پس به π[q − 1] برمی‌گردیم.

    محاسبه

    خود جدول هم با همین ایده ساخته می‌شود: اگر P[k] = P[q] باشد مرز یکی بلندتر می‌شود؛ وگرنه به مرزِ بعدیِ کوتاه‌تر π[k − 1] برمی‌گردیم و دوباره امتحان می‌کنیم.

    هزینه

    k در کل حداکثر m بار زیاد می‌شود و هر برگشت آن را کم می‌کند؛ پس کل کار O(m) است (تحلیل سرشکن).

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

    • اشاره‌گرهای q و k روی الگو؛ جدول هر نویسه را با π اش نشان می‌دهد.