Introduction
ধরি আমাদের একটি স্ট্রিং $s$ দেয়া আছে। স্ট্রিংটির দৈর্ঘ্য $|s|$ ওই স্ট্রিং $s$ এর জন্য $z$-ফাংশন হচ্ছে একটি $|s|$ সাইজের অ্যারে, যেখানে $i$ তম উপাদান $z[i]$ হচ্ছে একটা স্বাভাবিক সংখ্যা, যেটা নির্দেশ করে $s$ এর $i$ তম ইনডেক্স থেকে শুরু করে সর্বোচ্চ কত বড় সাবস্ট্রিং নেওয়া যাবে যেন সেটা $s$ এর প্রিফিক্স হয়।
এই আর্টিকেলটিতে আমি ভেজাল এড়ানোর উদ্দেশ্যে সবকিছুর জন্য $0$-বেসড ইন্ডেক্স ধরে নিব ।
$z$-ফাংশনের প্রথম উপাদান এর ব্যাপারে নির্দিষ্ট করে কিছু নেই। এটা তেমন গুরুত্বপূর্ণ কিছু নয়। 😕 কারণ শূন্য থেকে শুরু করলে পুরোটা স্ট্রিংয়ের প্রিফিক্স এর সাথে সর্বদা ম্যাচ করবে। আমরা এখানে $z[0] =0 $ ধরে নিতে পারি। এই আর্টিকেলে আমি $z$-ফাংশন $O(n)$ কম্প্লেক্সিটি তে ক্যালকুলেট করার অ্যালগরিদম ও দেখাবো।
Examples
উদাহরণ হিসেবে, নিচে কিছু স্ট্রিং এর $z$-ফাংশনের সবগুলো মান বের করে দেওয়া হলো: 😀
- “$aaaaa$” - $[0,4,3,2,1]$
- “$aaabaab$” - $[0,2,1,0,2,1,0]$
- “$abacaba$” - $[0,0,1,0,3,0,1]$
Trivial Algorithm
ডেফিনেশন থেকে চাইলে নুবের মতো $O(n^2)$ কোড লিখে ফেলা যায়। 😒
vector<int> z_function_trivial(string s) {
int n = (int) s.length();
vector<int> z(n);
for (int i = 1; i < n; ++i)
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
return z;
}
আমরা শুধু প্রতিটা পজিশন $i$ এর জন্য লুপ চালিয়ে যতক্ষণ স্ট্রিংটির প্রিফিক্সের সাথে মিলতে থাকবে ততক্ষণ পর্যন্ত $z[i]$ এর মান বাড়াতে থাকবো। এটা অবশ্যই ফালতু একটা অ্যালগোরিদম। এই টাইম কম্প্লেক্সিটির চেয়ে অনেক ভালোভাবে $z$-ফাংশন ক্যালকুলেট করা যায়। এবার আমরা সেটা দেখবো। 😍
Efficient algorithm to compute the Z-function
একটা এফিশিয়েন্ট অ্যালগরিদম তৈরি করার জন্য আমরা $z[i]$ এর মানগুলো $i=1$ থেকে $n-1$ পর্যন্ত কম্পিউট করবো। কিন্তু আমরা চেষ্টা করব আগের কম্পিউট করা মানগুলো কে যতটা সম্ভব কাজে লাগানোর।
ঝামেলা এড়ানোর জন্য আমরা “সেগমেন্ট ম্যাচ” বলতে ওই সাবস্ট্রিং গুলোকে বুঝাবো যেগুলো $s$ এর কোন একটি প্রিফিক্স এর সাথে ম্যাচ করে। যেমন, $z$-ফাংশনের ভ্যালু $z[i]$ হচ্ছে ওই সেগমেন্ট ম্যাচের দৈর্ঘ্য যা $i$ তে শুরু এবং $i+z[i]-1$ এ শেষ।
এটা করার জন্য আমরা $l$ ও $r$ রাখবো যেই $[l:r]$ রেঞ্জটি নির্দেশ করবে $r$ এ শেষ এমন একটি সেগমেন্ট ম্যাচ $l$ এ শুরু। আরেকভাবে $r$ একটা বাউন্ডারি হিসেবে দেখা যায় যেটা নির্দেশ করে যে এতোটুকু পর্যন্ত আমাদের কাজ করা হয়েছে এবং এর পরের সবকিছু এখনো পর্যন্ত আমাদের অজানা।
এখন, মনে করি আমরা $i$ তম ইনডেক্সে আছি। এখন আমাদের $z[i]$ এর মান ক্যালকুলেট করতে হবে। এক্ষেত্রে দুটি কেস থাকতে পারে।
-
$i>r$ – বর্তমান ইনডেক্সটি আমরা যতটুকু পর্যন্ত প্রসেস করেছি এর বাইরে। এক্ষেত্রে আমরা ট্রিভিয়াল এলগরিদম এর মতই জাস্ট লুপ চালিয়ে একটি একটি করে ভ্যালু চেক করতে থাকবো। এখানে এই জিনিসটা খেয়াল রাখতে হবে যে আমাদের $r$ এর মান পরিবর্তন করতে হবে কারণ এটা নিশ্চিত যে $r$ এর বর্তমান মান আগের $r$ এর চেয়ে বেশি হবে।
-
$ i \leq r$ – বর্তমান পজিশনটা আমরা যতটুকু প্রসেস করেছি এর ভিতর। এখন আমরা আগের ক্যালকুলেট করা $z[]$ এর মান গুলোর সাহায্যে $z[i]$ তে কোন একটা মান এসাইন করব । তারপর আমরা ওই মান থেকে কাজ করা শুরু করব। এটা অবশ্যই $0$ থেকে কাজ শুরু করার চেয়ে ভালো। আমরা একটু খেয়াল করলেই দেখতে পাবো যে $s[l…….r]$ এবং $s[0…….r-l]$ কিন্তু পুরোপুরি ম্যাচ করবে। এটা কেন হবে এটা আমরা কিছুটা চিন্তা করলেই বুঝতে পারব।
$[0, r-l]$ অংশটির $z$-ভেলু আগে থেকেই ক্যালকুলেট করা আছে। তাই আমরা চাইলে $z[i]$ এর ভ্যালু হিসেবে $z[i-l]$ কে ধরে নিতে পারি।
কিন্তু এখানে একটি বিষয় আছে, $z[i-l]$ এর মান অনেক বড় হয়ে যেতে পারে। যে সেটা যদি $i$ এর $z$-ভ্যালু হয় তাহলে তা $i$ এর সাথে যুক্ত করলে $r$ এর চেয়ে বেশি হয়ে যায়। কিন্তু আমরা $r$ এর ডান এর মান গুলো সম্পর্কে কিছুই জানিনা। এটি মিলতে পারে, নাও মিলতে পারে। তাই আমরা $z[i]$ এর মান এত বেশি নিতে পারব না যে তা বর্তমান পজিশন এর সাথে যুক্ত করলে $r$ বেশি হয়ে যায় অর্থাৎ $i+z[i] > r$ হয়ে যায়। একটি উদাহরণ হতে পারে এমন:
$s =$ “$ aaaabaa$”
যখন আমরা শেষের আগের পজিশনে পৌঁছাব $(i=6)$, আমরা দেখতে পাচ্ছি যে বর্তমান সেগমেন্ট ম্যাচ হচ্ছে $[5:6]$, $6$ পজিশনটি তাহলে $6-5=1$ এর সাথে ম্যাচ করবে যেটার $z$-ফাংশনের মান হচ্ছে $z[1]=3$। অবশ্যই আমরা $z[6]$ এ $3$ এসাইন করতে পারি না কারন তাহলে এটা সম্পূর্ণ ভুল হবে। সর্বোচ্চ যে ভ্যালু আমরা নিতে পারি সেটা হচ্ছে 1। কারণ এটাই সর্বোচ্চ মান যেটা নিলেও $i+z[i]$ এর মান $r$ পার হবে না। তাই প্রাথমিকভাবে আমরা $z[i]$ এর মানে নিশ্চিত ভাবে এটা নিতে পারি:
$z[i] = min(r-i+1, z[i-l])$
প্রাথমিকভাবে মান বসানোর পর আমরা ট্রিভিয়াল অলগোরিদমের মতো লুপ চালিয়ে চেক করব তারপর আর কতটুকু ম্যাচ করে।
তাই এই অ্যালগরিদম টা মূলত দুই ভাগে বিভক্ত, যেগুলো শুধু $z[i]$ এর প্রাথমিক মান কত হবে সেটা দিয়ে আলাদা। প্রথম কেস এর ক্ষেত্রে আমরা প্রাথমিক মান হিসেবে 0 ধরে নেই। দ্বিতীয় ক্ষেত্রে আমরা পূর্ববর্তী ক্যালকুলেট করা মানগুলো কে বিবেচনা করে একটি ভ্যালু এসাইন করি। তারপর আমরা উভয় ক্ষেত্রেই ট্রিভিয়াল অ্যালগরিদম টি ব্যবহার করে বাকি মানগুলো ক্যালকুলেট করি।
কম্প্লেক্সিটি তুলনায় অ্যালগরিদমটি আসলে খুবই সরল. এখন অনেকের মনে সন্দেহ জাগতে পারে যে আমরা প্রতিটি ইন্ডেক্স এর জন্য ট্রিভিয়াল অ্যালগরিদম চালালাম, তাহলে কম্প্লেক্সিটি লিনিয়ার হলো কিভাবে। আমরা ইম্প্লেমেন্টেশন এর পরেই এটার প্রমাণ দেখব ।
Implementation
অ্যালগোরিদমের পিছনের আইডিয়ায় তুলনায় ইম্প্লিমেনটেশন খুবই ছোট
vector<int> z_function(string s) {
int n = (int) s.length();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r)
z[i] = min (r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}
সোর্স: E-Maxx