KMP
কেএমপি
Pattern-এর failure function (prefix table) আগে বানিয়ে রাখা string matching — mismatch-এ text-এর pointer পিছায় না, মোট খরচ O(n+m)।
also: knuth-morris-pratt, kmp algorithm, prefix function
Naive matching-এ mismatch হলে text pointer এক ঘর পিছায় — খারাপ case-এ O(n·m)। KMP-র ভাবনা: pattern-এ যা match হয়েছে তার prefix-suffix overlap আগেই হিসেব করে রাখা।
pattern: a b a b a c
failure: 0 0 1 2 3 0Mismatch-এ pattern pointer failure[pos]-এ লাফ দেয় — যেটুকু তবুও match করা আছে সেটুকুই। Text pointer কখনো পিছায় না, তাই scan phase O(n), preprocessing O(m)।
Failure function নিজেও আগের ঘর দেখে DP-র মতোই বানানো হয়; streaming text-এ “pointer কখনো পিছায় না” গ্যারান্টিটা KMP-র নিজস্ব।