KMP (Knuth-Morris-Pratt algorithm)


KMP কি?

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

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

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

#include<bits/stdc++.h>
char T[10000];
char P[10000];
int main()
{
    scanf("%s %s",T,P);
    for(int i=0;T[i];i++)
    {
        bool flag=true;
        for(int j=0;P[j];j++)
        {
            if(P[j]!=T[i+j])
            {
                flag=false;
                break;
            }
        }
        if(flag)std::cout<<"match at position "<<i<<std::endl;
    }
    return 0;
}

উপরে 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 স্ট্রিং আছে [x1x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13] এমন।
Capture

এখন T স্ট্রিং এর সাথে P স্ট্রং ম্যাচ করতে করতে x8, Pমিস ম্যাচ হল, তাহলে π[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”

prefix

π array calculation steps:

vector<int> compute_prefix(const char *p)
{
    int m=strlen(p+1);
    vector<int> prefix(m+1);
    prefix[1]=0;
    int k=0;
    for(int i=2; i<=m; i++)
    {
        while(k>0 and p[k+1]!=p[i])k=prefix[k];
        if(p[k+1]==p[i])k=k+1;
        prefix[i]=k;
    }
    return prefix;
}

KMP-Matcher:

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

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

123 4 5 6 7 8 9 10 11 12 Capture 14 15 16 17

vector<int> KMP_match(const char *txt,const char *ptrn)
{
    int n=strlen(txt+1);
    int m=strlen(ptrn+1);
    vector<int> Prefix=compute_prefix(ptrn);
    vector<int>Match_position;
    int q=0;
    for(int i=1; i<=n; i++)
    {
        while(q>0 and ptrn[q+1]!=txt[i])q=Prefix[q];
        if(ptrn[q+1]==txt[i])q=q+1;
        if(q==m)
        {
            Match_position.push_back(i-m);
            q=Prefix[q];
        }
    }
    return Match_position;
}

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]
দেখা যাচ্ছে while loop এর প্রতি iteration এ k time decrease হচ্ছে।
তারমানে পুরো for loop এ while loop total m-1 time iterate হচ্ছে। সুতরাং prefix function er runtime হচ্ছে, Θ(m)।
একইভাবে kmp matcher function এর runtime analysis করা যায় Θ(n)।
সুতরাং kmp algorithm এর total complexity: Θ(n+m).

All together:

#include<bits/stdc++.h>
using namespace std;
char TXT[10000000],ptr[10000000];
vector<int> Match_position;
vector<int> compute_prefix(const char *p)
{
    int m=strlen(p+1);
    vector<int> prefix(m+1);
    prefix[1]=0;
    int k=0;
    for(int i=2; i<=m; i++)
    {
        while(k>0 and p[k+1]!=p[i])k=prefix[k];
        if(p[k+1]==p[i])k=k+1;
        prefix[i]=k;
    }
    return prefix;
}
vector<int> KMP_match(const char *txt,const char *ptrn)
{
    int n=strlen(txt+1);
    int m=strlen(ptrn+1);
    vector<int> Prefix=compute_prefix(ptrn);
    vector<int>Match_position;
    int q=0;
    for(int i=1; i<=n; i++)
    {
        while(q>0 and ptrn[q+1]!=txt[i])q=Prefix[q];
        if(ptrn[q+1]==txt[i])q=q+1;
        if(q==m)
        {
            Match_position.push_back(i-m);
            q=Prefix[q];
        }
    }
    return Match_position;
}
int main()
{
    scanf("%s %s",TXT+1,ptr+1);
    vector<int> Match_position=KMP_match(TXT,ptr);
    for(int i=0; i<Match_position.size(); i++)
    {
        if(!i)printf("%d",Match_position[i]);
        else printf(" %d",Match_position[i]);
    }
    return 0;
}

ইনপুট নেয়া লাগবে 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 😀 😀

Advertisements

About Tanvir Hasan Anick

I can read and write code, :)
This entry was posted in algorithm and tagged , . Bookmark the permalink.

3 Responses to KMP (Knuth-Morris-Pratt algorithm)

  1. Rajon Bardhan says:

    The Pictures are very helpful .
    Thanks .

    Liked by 1 person

  2. very helpful for student who want learn algorithm in bangla………………………..

    Like

  3. Pingback: KMP অ্যালগোরিদম – return 0;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s