প্যাটার্ন ম্যাচিং অ্যালগরিদম

প্যাটার্ন ম্যাচিং অ্যালগরিদম কম্পিউটার সায়েন্সে খুবই গুরুত্বপূর্ণ।আমরা যখন ডাটাবেসে বা ওয়েব ব্রাউজারে স্ট্রিং সার্চ করি তখন সার্চ রেজাল্ট দেখানোর জন্য এই অ্যালগরিদম ইউজ হয়।একটা বেসিক প্যাটার্ন ম্যাচিং প্রবলেম হলঃ একটা টেক্সট স্ট্রিং এবং প্যাটার্ন স্ট্রিং দেওয়া থাকবে,খুঁজে দেখতে হবে টেক্সট স্ট্রিং এর মধ্যে প্যাটার্ন স্ট্রিং টা আছে কি না।এই প্রবলেম টা "The needle in a haystack problem" নামেও পরিচিত।

Naive Approach:

Naive method টা হল straightforward।টেক্সট স্ট্রিং এর প্রতিটা পজিশনকে প্যাটার্ন স্ট্রিং এর শুরুর পজিশন বিবেচনা করে দেখতে হবে ম্যাচ পাওয়া যায় কি না।

Sample code:

	#include<bits/stdc++.h>
	using namespace std;
	int main()
	{
	char Text[100],Pat[100];
	gets(Text); //Enter the text string
	gets(Pat); //Enter he pattern string to be searched
	for(int i=0;Text[i];i++){
	for(int j=0;Pat[j];j++){
	if(Text[i+j]!=Pat[j])break; //if not match,break inner loop
	if(j==strlen(Pat)-1) printf("Pattern found at %d",i);
	}
	}
	return 0;
	}

view raw Naive Approach(patter matching).cpp hosted with ❤ by GitHub

Naive approach যদিও বুঝা খুব সহজ,কিন্তু খুব স্লো।যদি টেক্সট স্ট্রিং এবং প্যাটার্ন স্ট্রিং এর লেন্থ যথাক্রমে n এবং m হয় তাহলে worst case এ সার্চ কমপ্লিট হতে (n*m) টি ইটারেশন লাগতে পারে।সুতরাং এর কমপ্লেক্সিটি হচ্ছে O(n*m)।

নুথ-মরিস-প্র্যাট(KMP) অ্যালগরিদমঃ

KMP অ্যালগরিদম Naive approach এর O(n*m) কমপ্লেক্সিটি কে O(n) তে নামিয়ে নিয়ে আসে।KMP এর বেসিক আইডিয়া হল Failure Function/Prefix Function।জিনিস টা হল এমন ধর,তুমি একটা টেক্সট স্ট্রিং  AAABAAAA মধ্যে প্যাটার্ন স্ট্রিং AAAA খুঁজছো।খুঁজতে খুঁজতে B তে গিয়ে বাঁশ খেয়ে গেলে,এখন কী করবে? Naive approach হলে আবার টেক্সট স্ট্রিং এর ২য় A কে প্যাটার্ন স্ট্রিং এর শুরু ধরে ম্যাচ করাতে চেষ্টা করতা।কিন্তু তুমি তো দিব্য দৃষ্টিতে দেখতে পাচ্ছো যে টেক্সট স্ট্রিং এর ২য় এবং ৩য় লেটার প্যাটার্ন স্ট্রিং এর ১ম ও ২য় লেটারের সাথে এমনি ম্যাচ করবে।তাইলে তো তুমি চাইলেই এই দুইটা ইটারেশন স্কিপ করতে পারো।এটাই হল KMP এর অপটিমাইজেশন। এখন প্রশ্ন হল,কিভাবে বুঝবো কয়টা ইটারেশন স্কিপ করতে পারব।এইটা জানা যাবে Failure Function/Prefix Function থেকে।

Failure Function/Prefix Function: 

KMP অ্যালগরিদম m লেন্থের একটি প্যাটার্ন স্ট্রিং pat[] কে প্রি-প্রসেস করে একই লেন্থের lps[] অ্যারে কনস্ট্রাক্ট করে যেটা ইটারেশন স্কিপ করতে ব্যবহার হবে। এখানে lps হল Longest proper prefix which is also a suffix...lps শব্দটাকে এভাবেও বলা যেতে পারে Longest prefix which is also a proper suffix. অর্থাৎ যেকোন একটা প্রোপার নিলেই হবে।তাহলে জেনে নেওয়া যাক Proper prefix & suffix আসলে কী?

সঠিক উপসর্গ (Proper Prefix)  ঃএকটা শব্দ যদি "ABCDBC" হয় তাহলে তার Proper Prefix গুলোর সেট হবে {"A","AB","ABC","ABCD","ABCDB"}।আর Proper prefix না হয়ে যদি শুধু prefix বলা হয় তাহলে "ABCDBC" ও সেটের অন্তর্ভুক্ত হবে।

সঠিক প্রত্যয়(Proper Suffix)  ঃ একটা শব্দ যদি "ABCDBC" হয় তাহলে তার Proper Suffix গুলোর সেট হবে {"C","BC","DBC","CDBC","BCDBC"}।আর Proper suffix না হয়ে যদি শুধু suffix বলা হয় তাহলে "ABCDBC" ও সেটের অন্তর্ভুক্ত হবে।

এখন কিভাবে একটি  lps[] অ্যারে কনস্ট্রাক্ট কিভাবে করতে হয় এবং KMP সার্চ কিভাবে কাজ করে তা আমরা GeeksforGeeks  এবং Topcoder থেকে শিখে নিতে পারি।আর এগুলো ভিজুয়ালাইজ করতে পারি এখান থেকে।

KMP এর সম্পূর্ণ কোডঃ

	#include<bits/stdc++.h>
	using namespace std;
	void Failure_Function(char* pat,int m,int lps[]){
	int len=0;
	lps[0]=0;
	int i=1;
	while(i<m){
	if(pat[i]==pat[len]){
	len++;
	lps[i]=len;
	i++;
	}
	else{
	if(len!=0) len=lps[len-1];
	else{
	lps[i]=0;
	i++;
	}
	}
	}
	}
	void kmp(char* text,char* pat){
	int n=strlen(text);
	int m=strlen(pat);
	int lps[m];
	Failure_Function(pat,m,lps);
	int i=0; //index for text
	int j=0; //index for pat
	while(i<n){
	if(text[i]==pat[j]){
	i++; j++;
	}
	if(j==m){
	printf("pattern found at idex %d\n",i-j);
	j=lps[j-1];
	}
	else if (i<n && pat[j]!=text[i]){
	if(j!=0) j=lps[j-1];
	else
	i=i+1;
	}
	}
	}
	int main()
	{
	char text[100],pat[100];
	gets(text); //Enter the text string
	gets(pat); //Enter the pattern string
	kmp(text,pat);
	return 0;
	}

view raw KMP.cpp hosted with ❤ by GitHub

KMP Related Problems & Solutions:

1. SPOJ NHAY - A Needle in the Haystack, LightOj-1255 (Substring Frequency) 

            Solution Idea: Straightforward.Simple implementation of KMP

            Solution: https://ideone.com/jV2n7D

2. SPOJ FINDSR - Find String Roots 

            Solution Idea: Construct an array lps[] of length m using failure function.where m is the length of the string.Return say t=lps[m]...if(m-t) divides m then ans is m/(m-t) else ans=1.

            Solution: https://ideone.com/i8EiA3

References:

→http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

→https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-string-searching-algorithms/ 

→https://people.ok.ubc.ca/ylucet/DS/KnuthMorrisPratt.html