KMP (Knuth–Morris–Pratt) متن را با O(n + m) مقایسه جستوجو میکند. پس از ناهمخوانی، از ساختار پیشوندیِ خودِ الگو تصمیم میگیرد چه مقدار از تطابق را نگه دارد.
KMP algorithm
جستوجوی رشته با یک تابع شکست از پیش محاسبهشده، بهطوری که اشارهگر متن هرگز عقب نمیرود.