الگوریتم KMP

مسئله جستجوی الگو

پیدا کردن همه محل‌های الگو P در متن T. روش ساده: هر محل شروع را امتحان کن — O(n×m). KMP آن را به O(n+m) می‌رساند!

بینش کلیدی: اطلاعات از مقایسه‌های قبلی

وقتی در متن «ABABD» الگوی «ABABD» را می‌جوییم و بعد از ۴ تطابق (ABAB) به عدم تطابق می‌رسیم، روش ساده به محل بعدی برمی‌گردد و از اول شروع می‌کند — اما ما می‌دانیم ۳ کاراکتر قبلی BAB است!

KMP این دانش را با جدول LPS (Longest Proper Prefix which is also Suffix) ذخیره می‌کند: بعد از عدم تطابق، الگو را «هوشمندانه» جابه‌جا می‌کند نه به ابتدا!

جدول LPS چیست؟

برای هر پیشوند الگو، طولانی‌ترین پسوند برابر با پیشوند (خودش نه):

الگو: "ABABC"

i=0: "A"     LPS=0 (پیشوند غیربدیهی ندارد)
i=1: "AB"    LPS=0
i=2: "ABA"   LPS=1 ("A" هم پیشوند هم پسوند)
i=3: "ABAB"  LPS=2 ("AB")
i=4: "ABABC" LPS=0

چرا جواب می‌دهد؟

وقتی تطابق j کاراکتری داشتیم و خراب شد، LPS[j−1] می‌گوید: «j کاراکتر تطبیقی، با LPS کاراکتر ابتدایش را می‌دانی که با پیشوند الگو برابر است — از آنجا ادامه بده!» بدون برگشت در متن!

الگوریتم

1. ساخت LPS الگو: O(m) — خودش با ایده تطبیق پیشوند/پسوند
2. اسکن متن: i فقط جلو می‌رود؛ در عدم تطابق j = LPS[j−1]

مثال کامل

متن:  ABABDABABC
الگو: ABABC (LPS = [0,0,1,2,0])

i=0..3: تطابق ABAB
i=4: D≠C خراب! j=LPS[3]=2 -> الگو ۲ جلو (نه از اول!)
i=4..: B≠A خراب، j=LPS[1]=0
... i=7: تطابق کامل ABABC ✓ محل ۵

جمع‌بندی

• KMP: جستجوی الگو در O(n+m)
• قلب: جدول LPS — دانش از تطبیق‌های قبلی
• متن هرگز به عقب برنمی‌گردد!
• کاربرد: جستجو، تشخیص تکرار، فشرده‌سازی