Knuth–Morris–Pratt(KMP) algorithm এর searching approach, নরমাল naive approach এর থেকে আলাদা।

Time Complixity: Naive approach O(m*n) KMP এর O(m+n)

স্বাভাবিক ভাবেই KMP algo ভাল ।

একটা জিনিষ ভোগাচ্ছিল, C++ এর string searching কি naive approach ব্যাবহার করে,নাকি KMP অথবা আরো ভাল কোন algo ব্যাবহার করে? শেষে পেলাম, "In essence if you're just looking for a substring, there is no reason to implement something like KMP because the library version will be roughly as fast as yours."

লিঙ্ক: http://old.blog.phusion.nl/…/06/efficient-substring-search…/

বুজলাম যে,string টা খুব একটা বড় না হলে , সাধারণ C++:string:find() ব্যাবহার করাই ভাল।তবে Time Complexity এর খেলা শুরু হলে naive approach আর কার্যকরী নয়, KMP এর মত algo লাগবেই।

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm