الگوریتم KMP
Knuth–Morris–Prattالگوریتم KMP یک الگوریتم از دسته رشته‌ها است. این الگوریتم رشته‌ای روی characterها، prefix/suffix یا state تطبیق/ویرایش کار می‌کند و تلاش می‌کند مقایسه‌های تکراری را کم کند.
اول این مفهوم را در ذهن نگه دار
الگوریتم KMP یک الگوریتم از دسته رشته‌ها است. این الگوریتم رشته‌ای روی characterها، prefix/suffix یا state تطبیق/ویرایش کار می‌کند و تلاش می‌کند مقایسه‌های تکراری را کم کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم الگوریتم KMP ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
فرض‌های Unicode، case و normalization را روشن کن.
indexها یا prefix state را تعریف کن.
اگر الگوریتم اجازه می‌دهد اطلاعات match قبلی را reuse کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم KMP هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی جست‌وجو روی متن بزرگ یا تکراری است و روش naive گران می‌شود از الگوریتم تخصصی استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن Unicode.
- قاطی کردن Substring و Subsequence.
- خطای index/prefix.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای الگوریتم KMP در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
الگوریتم KMP چه مسئله‌ای را حل می‌کند؟
الگوریتم KMP یک الگوریتم از دسته رشته‌ها است. این الگوریتم رشته‌ای روی characterها، prefix/suffix یا state تطبیق/ویرایش کار می‌کند و تلاش می‌کند مقایسه‌های تکراری را کم کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن Unicode.