C-তে প্যাটার্ন ম্যাচিং (Pattern Matching) − আমাদের চেক করতে হবে একটি স্ট্রিং অন্য একটি স্ট্রিংয়ে উপস্থিত কিনা, উদাহরণস্বরূপ, স্ট্রিং "algorithm" স্ট্রিং "naive algorithm" এর মধ্যে উপস্থিত। যদি পাওয়া যায়, তবে তার লোকেশন (অর্থাৎ কোন পজিশনে আছে) ডিসপ্লে করা হয়। আমরা একটি ফাংশন তৈরি করি যা দুটি ক্যারেক্টার অ্যারে নেয় এবং ম্যাচ হলে পজিশন রিটার্ন করে অন্যথায় -1 রিটার্ন করে।
Input: txt = "HERE IS A NICE CAP" pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX" pattern = "XYZX"
Output: Pattern found at index 0
Pattern found at index 9
Pattern found at index 12
আমরা এই সমস্যাটি নেইভ প্যাটার্ন সার্চিং (Naive Pattern Searching) দিয়ে সমাধান করছি। এই অ্যালগরিদম ছোট টেক্সটের জন্য উপযোগী। নেইভ (Naive) হল একটি সিম্পল এবং অদক্ষ (inefficient) পদ্ধতি যেখানে একটি স্ট্রিং অন্য স্ট্রিংয়ে কোথায় থাকতে পারে সেটা এক এক করে সব জায়গা চেক করে দেখা হয়।
নেইভ অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(mn), যেখানে m হল সার্চ করার প্যাটার্নের সাইজ এবং n হল কন্টেইনার স্ট্রিংয়ের সাইজ।
প্যাটার্ন সার্চিং কম্পিউটার সায়েন্স-এ একটি খুব গুরুত্বপূর্ণ সমস্যা। যতবার আমরা নোটপ্যাড/ওয়ার্ড ফাইল বা ব্রাউজার বা ডাটাবেস বা অন্য কোথাও একটি স্ট্রিং সার্চ করি, প্যাটার্ন সার্চিং অ্যালগরিদমই সার্চ রেজাল্ট দেখানোর জন্য ব্যবহৃত হয়।
আলগরিদম (Algorithm)
naive_algorithm(pattern, text)
ইনপুট (Input) − টেক্সট (text) এবং প্যাটার্ন (pattern)
আউটপুট (Output) − লোকেশনগুলো, যেখানে প্যাটার্নটি টেক্সটে উপস্থিত।
Start
pat_len := pattern Size
str_len := string size
for i := 0 to (str_len - pat_len), do
for j := 0 to pat_len, do
if text[i+j] ≠ pattern[j], then
break
if j == patLen, then
display the position i, as there pattern found
End
উদাহরণ (C প্রোগ্রাম)
#include <stdio.h>
#include <string.h>
int main() {
char txt[] = "tutorialsPointisthebestplatformforprogrammers";
char pat[] = "a";
int M = strlen(pat);
int N = strlen(txt);
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M)
printf("Pattern matches at index %d\n", i);
}
return 0;
}
আউটপুট
Pattern matches at 6 Pattern matches at 25 Pattern matches at 39
ব্যাখ্যা: নেইভ অ্যালগরিদম ব্রুট-ফোর্স (brute-force) পদ্ধতি। টেক্সটের প্রতিটি পজিশন থেকে প্যাটার্ন ম্যাচ চেক করা হয়। এটি সিম্পল কিন্তু বড় টেক্সটের জন্য ধীর। রাবিন-কার্প, KMP, বয়ার-মুর (Boyer-Moore) ইত্যাদি অ্যালগরিদম দ্রুততর।
