KMP (Knuth-Morris-Pratt algorithm)

KMP কি?

kmp স্ট্রিং ম্যাচিং এ্যালগরিদম। Kmp লিনিয়ার টাইমে একটা স্ট্রিং T তে একটা প্যাটার্ন স্ট্রিং P কতবার আছে এবং কোন কোন পজিশনে আছে তা বের করে।

KMP কিভাবে কাজ করে?

Kmp কিভাবে কাজ করে তা বুঝার আগে একটা স্ট্রিং T থেকে প্যাটার্ন স্ট্রিং P কতবার ও কোথায় আছে তার naive solution টা দেখে নেয়া জরুরী।

Naive solution:

উপরে solution এ T এর প্রতি পজিশন থেকে P স্ট্রিং ম্যাচ করে দেখা হচ্ছে এবং কোথাও ম্যাচ না পেলে আবার P স্ট্রং এর প্রথম পজিশনে গিয়ে ম্যাচ করে দেখা হচ্ছে।
Kmp এ্যালগরিদম ম্যাচ না পেলে P স্ট্রিং এর বার বার প্রথম পজিশন এ গিয়ে ম্যাচ করানোর জিনিস টা স্কিপ করে।
Kmp এ্যালগরিদমে একটা ফাংশন থাকে যাকে prefix/π/failure ফাংশন বলা হয়ে থাকে।
এই ফাংশন একটা π এ্যারে তৈরী করে দেয়, যাতে প্যাটার্ন স্ট্রিং P এর সব পজিশনে কতটুক প্রিফিক্স ম্যাচ করে তা থাকে।

যখনেই T স্ট্রিং এর কোন পজিশন এ P এর স্ট্রিং এর কোন পজিশন মিস ম্যাচ হবে, তখন π এ্যারে দেখে P স্ট্রিং এর কোন পজিশনে যাবে তা নির্ধারন করা হয়।
ধরা যাক P স্ট্রিং [_{P1P2,P3,P4,P5,P6}] এর π এ্যারে [0,0,1,2,3,0,1] এমন।
এখন একটা T স্ট্রিং আছে [x₁x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x₁₀,x₁₁,x_12,x₁₃] এমন।

এখন T স্ট্রিং এর সাথে P স্ট্রং ম্যাচ করতে করতে x_8, P5 মিস ম্যাচ হল, তাহলে π[5] পজিশন এ জাম্প করবে এবং দেখবে P স্ট্রিং এর পরের পজিশন T এর current পজিশনের সাথে ম্যাচ করে নাকি। যদি ম্যাচ করে তাহলে পরবর্তী সার্চ সেখান থেকে শুরু হবে। কারন আমি T স্ট্রিং এর সাথে P স্ট্রং এর π[5] পর্যন্ত প্রিফিক্স ম্যাচ করে আসেছি। আর যদি ম্যাচ না করে তাহলে সেই পজিশনের π পজিশনে আবার জাম্প করবে ঠিক করবে কোথায় থেকে ম্যাচিং শুরু করবে।

Compute Prefix/Failure function:

Here Green character need to match, Red character mismatch, Blue character match.

Pattern string: “ababaca”

π array calculation steps for this string

 Compute prefix/failure function:

KMP-Matcher:

Here Blue part current matching, Green part previously match and Red part current mismatch.

Text String T=”ababababacaab”, Pattern String P=”ababaca”

KMP_match:

Complexity analysis:

Compute prefix function এ লাইন 9 while loop execute হবে O(m) times. এখন k=0 এবং 7-12 লাইনে for loop এ k সর্বোচ্চ প্রতিবার বাড়তে পারে আর k এর সর্বোচ্চ মান মনে m-1।
আবার k<i এবং π[i]
সুতরাং kmp algorithm এর total complexity: Θ(n+m).

All together:

ইনপুট নেয়া লাগবে index 1 থেকে।

Reference:
1. Introduction to Algorithms – Cormen
2. wiki 

Practice problem:

1. Ministry of Truth
2. Jack’s Last Word
3. Substring Frequency
4. Making Huge Palindromes
   

বিদ্রঃ কোথায় ভুল থাকলে বা বুঝতে সমস্যা হলে কমেন্টে জানানোর জন্য অনুরোধ করা হল।

Happy Coding 😀 😀