KMP یک الگوی متنیِ مشخص را به‌صورت دقیق در متن پیدا می‌کند و جای همهٔ رخدادها را می‌دهد؛ از جمله رخدادهایی که با هم هم‌پوشانی دارند. ایده این است که پس از ناسازگاریِ نویسه، اطلاعاتِ بخشِ تطبیق‌یافته را دور نریزیم. تابعِ پیشوند مشخص می‌کند کدام بخش از الگو هنوز می‌تواند با انتهایِ خوانده‌شدهٔ متن برابر باشد. این جست‌وجو معنایی، اصلاح غلط تایپی یا اجرای مدل زبانی نیست.
یک الگو و جدولِ پیشوندش
الگوی ساختگیِ ما abaabab است. برای هر جایگاه، π طولِ بلندترین پیشوندِ «کوچک‌تر از کلِ همان بخش» است که پسوندِ آن بخش نیز باشد. واژهٔ proper مهم است؛ اگر خودِ بخش را مجاز بگیریم، همهٔ خانه‌ها طولِ همان بخش می‌شوند و بازگشتِ مفید نداریم.
| جایگاه صفرمبنا | نویسه | π |
|---|---|---|
| ۰ | a | ۰ |
| ۱ | b | ۰ |
| ۲ | a | ۱ |
| ۳ | a | ۱ |
| ۴ | b | ۲ |
| ۵ | a | ۳ |
| ۶ | b | ۲ |
برای بخشِ شش‌نویسه‌ای abaaba، پیشوند و پسوندِ aba طول۳ دارند. برای کلِ abaabab، بلندترینِ مناسب ab با طول۲ است. کد علاوه بر ساختِ خطیِ π، روی الگوهای کوتاه همهٔ طول‌هایِ مجازِ پیشوند و پسوند را مستقل مقایسه می‌کند؛ صرفاً یک جدولِ ازقبلنوشته‌شده را چاپ نمی‌کند.
بازگشت بدون عقب‌بردنِ متن
متنِ آموزشی abaabaabababaabab است. متغیر j تعداد نویسه‌هایِ فعلاً تطبیق‌یافته از ابتدای الگو را نگه می‌دارد. اگر نویسهٔ تازه با نویسهٔ بعدیِ الگو ناسازگار باشد، j به π[j−۱] برمی‌گردد و همان نویسهٔ متن دوباره با این نامزدِ کوتاه‌تر سنجیده می‌شود؛ اشاره‌گرِ متن عقب نمی‌رود.
در اجرای واقعی، در جایگاه۶ متن با نویسهٔ a، طولِ تطبیق از۶ به۳ برمی‌گردد. بعداً در جایگاه۱۱ با b، از۳ به۱ برمی‌گردد. هر دو رویداد با جایگاه، نویسه و طولِ قبل و بعد در JSON هستند. خروجیِ شروعِ رخدادهای کامل [۳،۱۰] است؛ همهٔ جایگاه‌ها صفرمبنا و هر دو برشِ متن واقعاً برابر الگوی هفت‌نویسه‌ای‌اند.
شمارندهٔ داخلِ تابع، در همین نمونهٔ اصلی 35 مقایسهٔ واقعیِ نویسه در مرحلهٔ تطبیق ثبت می‌کند؛ بررسیِ شرطِ while و if هر دو حساب می‌شوند، حتی اگر در یک گام دوباره برابر‌بودن سنجیده شود. ساختِ π و اجرای oracle در این عدد نیستند. این عدد فقط رفتارِ همین کد و ورودی است؛ مقایسهٔ سرعت با سرویس یا همهٔ پیاده‌سازی‌های KMP نیست.
پس از موفقیت هم اطلاعات را دور نریزیم
برای الگوی aaa در متن aaaaa، جواب سه شروعِ [۰،۱،۲] است. اگر پس از یک موفقیت به‌اندازهٔ طولِ الگو جلو بپریم، رخدادهای هم‌پوشان از دست می‌روند. فایل بعد از ثبتِ یک رخداد، j را به پیشوندِ مناسبِ همان الگوی کامل برمی‌گرداند و خواندنِ متن ادامه می‌یابد.
تابع مستقلِ ساده برای هر جایگاهِ ممکن، برشِ هم‌طولِ متن را مستقیماً با الگو مقایسه می‌کند. همهٔ متن‌های الفبای a و b با طولِ صفر تا۶، همراه همهٔ الگوهای طولِ۱ تا۳، مجموعاً۱۷۷۸جفت را واقعاً بررسی کرده‌ایم؛ فهرست رخدادها دقیقاً برابر است. این شمار، benchmark سرعت یا شاهدی دربارهٔ موتور جست‌وجوی یک محصول نیست.
جایگاهِ فارسی را با بایت اشتباه نگیریم
در رشتهٔ «می‌رویم، می‌رویم»، الگوی «می‌رویم» با همان نیم‌فاصله در شروع‌های۰ و۹ دیده می‌شود. واحدِ اندیس در این Python، code point یونیکد است؛ جایگاهِ بایتِ UTF-8 یا خوشهٔ نویسهٔ دیده‌شده نیست. حذفِ نیم‌فاصله یا تغییرِ علائم می‌تواند طول و جایگاه را عوض کند.
فایل هیچ نرمال‌سازیِ پنهانی ندارد: یِ فارسی و يِ عربی برابر نیستند و نمونهٔ تک‌نویسه‌ای هم این تفاوت را واقعاً کنترل می‌کند. الگوی خالی نیز طبق قراردادِ صریحِ این تمرین رد می‌شود؛ رفتارِ همهٔ توابعِ جست‌وجوی استاندارد دربارهٔ الگوی خالی را عین همین نگیرید.
کدام پرسش را با KMP جواب ندهیم؟
KMP رخدادِ دقیقِ یک الگو را پیدا می‌کند؛ معنیِ همسان، واژهٔ مرتبط، ریشهٔ فارسی یا جوابِ سؤال را تشخیص نمی‌دهد. برای چند الگو یا تطبیق تقریبی، طراحیِ مسئله و روش فرق می‌کند. توکن‌سازیِ BPE نیز واحدهای مدل را می‌سازد و این فهرستِ رخدادهای دقیق را جایگزین نمی‌کند.
ساخت π و پیمایشِ KMP در تحلیلِ متعارف مجموعاً زمانِ خطی نسبت به طولِ الگو و متن دارند؛ فایل زمان‌سنجیِ سرویس واقعی اجرا نکرده است. برای پاسخ‌گوییِ متکی به دانشِ سازمان، در مسیر چتِ سایت اپرا سؤالِ واقعی و منابعِ مجاز را مشخص کنید؛ این تمرین وجود KMP یا جست‌وجوی معناییِ خاصی در محصول را ثابت نمی‌کند.
فایل تمرین و منبع
کد کامل Python؛ محاسبه و کنترل‌های مستقل · ورودیِ ساخته‌شده، مراحل و خروجیِ اجرای واقعی
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.