জেড-ফাংশন এবং এর গণনা#

ধরা যাক, আমাদের $n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে। এই স্ট্রিংটির জন্য জেড-ফাংশন হলো $n$ দৈর্ঘ্যের একটি অ্যারে, যেখানে $i$-তম উপাদানটি হলো $i$ পজিশন থেকে শুরু করে সর্বাধিক যতগুলো ক্যারেক্টার $s$-এর প্রথম ক্যারেক্টারগুলোর সাথে মিলে যায় তার সংখ্যা।

অন্যভাবে বলতে গেলে, $z[i]$ হলো সবচেয়ে দীর্ঘ সেই স্ট্রিংটির দৈর্ঘ্য যেটি একই সাথে $s$-এর একটি প্রিফিক্স এবং $i$ থেকে শুরু হওয়া $s$-এর সাফিক্সের একটি প্রিফিক্স।

দ্রষ্টব্য: এই আর্টিকেলে অস্পষ্টতা এড়াতে আমরা $0$-ভিত্তিক ইনডেক্স ধরে নিচ্ছি; অর্থাৎ $s$-এর প্রথম ক্যারেক্টারের ইনডেক্স $0$ এবং শেষটির ইনডেক্স $n-1$।

জেড-ফাংশনের প্রথম উপাদান $z[0]$ সাধারণত সুসংজ্ঞায়িত নয়। এই আর্টিকেলে আমরা ধরে নেব এটি শূন্য (যদিও এটি অ্যালগরিদমের ইমপ্লিমেন্টেশনে কোনো পরিবর্তন আনে না)।

এই আর্টিকেলে $O(n)$ সময়ে জেড-ফাংশন গণনার একটি অ্যালগরিদম এবং এর বিভিন্ন অ্যাপ্লিকেশন উপস্থাপন করা হয়েছে।

উদাহরণ#

উদাহরণস্বরূপ, বিভিন্ন স্ট্রিংয়ের জন্য গণনা করা জেড-ফাংশনের মানগুলো এখানে দেওয়া হলো:

“aaaaa” - $[0, 4, 3, 2, 1]$
“aaabaab” - $[0, 2, 1, 0, 2, 1, 0]$
“abacaba” - $[0, 0, 1, 0, 3, 0, 1]$

সাধারণ অ্যালগরিদম#

আনুষ্ঠানিক সংজ্ঞাটিকে নিচের সরল $O(n^2)$ ইমপ্লিমেন্টেশনে উপস্থাপন করা যায়।

vector<int> z_function_trivial(string s) {
	int n = s.size();
	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[i] = 0$ থেকে শুরু করে এবং যতক্ষণ মিসম্যাচ না পাওয়া যায় (এবং যতক্ষণ লাইনের শেষে না পৌঁছাই) ততক্ষণ বাড়াচ্ছি।

অবশ্যই, এটি একটি দক্ষ ইমপ্লিমেন্টেশন নয়। এখন আমরা একটি দক্ষ ইমপ্লিমেন্টেশনের নির্মাণ দেখাব।

জেড-ফাংশন গণনার দক্ষ অ্যালগরিদম#

একটি দক্ষ অ্যালগরিদম পেতে আমরা $z[i]$-এর মানগুলো $i = 1$ থেকে $n - 1$ পর্যন্ত ক্রমান্বয়ে গণনা করব, কিন্তু একই সাথে একটি নতুন মান গণনা করার সময় পূর্বে গণনা করা মানগুলোকে যতটা সম্ভব কাজে লাগানোর চেষ্টা করব।

সংক্ষিপ্ততার জন্য, $s$-এর প্রিফিক্সের সাথে মিলে যাওয়া সাবস্ট্রিংগুলোকে আমরা সেগমেন্ট ম্যাচ বলব। উদাহরণস্বরূপ, কাঙ্ক্ষিত জেড-ফাংশনের $z[i]$ মানটি হলো $i$ পজিশনে শুরু হওয়া সেগমেন্ট ম্যাচের দৈর্ঘ্য (এবং এটি $i + z[i] - 1$ পজিশনে শেষ হয়)।

এটি করার জন্য, আমরা সবচেয়ে ডানদিকের সেগমেন্ট ম্যাচের $[l, r)$ ইনডেক্সগুলো সংরক্ষণ করব। অর্থাৎ, শনাক্ত করা সব সেগমেন্টের মধ্যে আমরা সেটি রাখব যেটি সবচেয়ে ডানদিকে শেষ হয়। একভাবে বলতে গেলে, $r$ ইনডেক্সটিকে একটি “সীমানা” হিসেবে দেখা যেতে পারে যেখান পর্যন্ত অ্যালগরিদম আমাদের স্ট্রিং $s$ স্ক্যান করেছে; সেই বিন্দুর পরের সবকিছু এখনও অজানা।

তাহলে, বর্তমান ইনডেক্স (যেটির জন্য আমাদের জেড-ফাংশনের পরবর্তী মান গণনা করতে হবে) যদি $i$ হয়, তবে দুটি সম্ভাবনা আছে:

$i \geq r$ – বর্তমান পজিশনটি আমরা ইতোমধ্যে যা প্রসেস করেছি তার বাইরে।
এক্ষেত্রে আমরা সাধারণ অ্যালগরিদম দিয়ে $z[i]$ গণনা করব (অর্থাৎ, একটির পর একটি মান তুলনা করে)। লক্ষ্য করুন, শেষে যদি $z[i] > 0$ হয়, তাহলে আমাদের সবচেয়ে ডানদিকের সেগমেন্টের ইনডেক্সগুলো আপডেট করতে হবে, কারণ নতুন $r = i + z[i]$ পূর্ববর্তী $r$-এর চেয়ে ভালো হবে এটি নিশ্চিত।
$i < r$ – বর্তমান পজিশনটি বর্তমান সেগমেন্ট ম্যাচ $[l, r)$-এর ভিতরে।
তাহলে আমরা ইতোমধ্যে গণনা করা জেড-মানগুলো ব্যবহার করে $z[i]$-কে একটি মান দিয়ে “ইনিশিয়ালাইজ” করতে পারি (এটি অবশ্যই “শূন্য থেকে শুরু করা"র চেয়ে ভালো), এমনকি হয়তো কোনো বড় সংখ্যা দিয়ে।
এর জন্য আমরা লক্ষ্য করি যে $s[l \dots r)$ এবং $s[0 \dots r-l)$ সাবস্ট্রিংগুলো মিলে যায়। এর অর্থ হলো $z[i]$-এর প্রাথমিক আনুমানিক মান হিসেবে আমরা $s[0 \dots r-l)$ সেগমেন্টের জন্য ইতোমধ্যে গণনা করা মানটি নিতে পারি, আর সেটি হলো $z[i-l]$।
তবে, $z[i-l]$-এর মান অনেক বড় হতে পারে: $i$ পজিশনে প্রয়োগ করলে এটি $r$ ইনডেক্সকে অতিক্রম করতে পারে। এটি অনুমোদিত নয় কারণ $r$-এর ডানদিকের ক্যারেক্টারগুলো সম্পর্কে আমরা কিছুই জানি না: সেগুলো প্রয়োজনীয় ক্যারেক্টারগুলো থেকে ভিন্ন হতে পারে।
এখানে অনুরূপ পরিস্থিতির একটি উদাহরণ দেওয়া হলো:
$$ s = "aaaabaa" $$
আমরা যখন শেষ পজিশনে ($i = 6$) পৌঁছাব, তখন বর্তমান ম্যাচ সেগমেন্ট হবে $[5, 7)$। পজিশন $6$, পজিশন $6 - 5 = 1$-এর সাথে মিলবে, যেটির জন্য জেড-ফাংশনের মান $z[1] = 3$। স্পষ্টতই, আমরা $z[6]$-কে $3$ দিয়ে ইনিশিয়ালাইজ করতে পারি না, এটি সম্পূর্ণ ভুল হবে। সর্বোচ্চ যে মান দিয়ে আমরা এটি ইনিশিয়ালাইজ করতে পারি তা হলো $1$ – কারণ এটিই সবচেয়ে বড় মান যা আমাদের ম্যাচ সেগমেন্ট $[l, r)$-এর $r$ ইনডেক্সের বাইরে নিয়ে যায় না।
সুতরাং, $z[i]$-এর প্রাথমিক আনুমানিক মান হিসেবে আমরা নিরাপদে নিতে পারি:
$$ z_0[i] = \min(r - i,\; z[i-l]) $$
$z[i]$-কে $z_0[i]$ দিয়ে ইনিশিয়ালাইজ করার পর, আমরা সাধারণ অ্যালগরিদম চালিয়ে $z[i]$ বাড়ানোর চেষ্টা করি – কারণ সাধারণভাবে, $r$ সীমানার পরে সেগমেন্টটি মিলতে থাকবে কি না তা আমরা জানতে পারি না।

এভাবে, পুরো অ্যালগরিদমটি দুটি কেসে বিভক্ত, যেগুলো শুধু $z[i]$-এর প্রাথমিক মানে পার্থক্য: প্রথম কেসে এটি শূন্য ধরা হয়, দ্বিতীয় কেসে এটি পূর্বে গণনা করা মানগুলো দ্বারা নির্ধারিত হয় (উপরের সূত্র ব্যবহার করে)। এরপর, অ্যালগরিদমের উভয় শাখাই সাধারণ অ্যালগরিদমের ইমপ্লিমেন্টেশনে নেমে আসে, যেটি প্রাথমিক মান নির্দিষ্ট করার পরপরই শুরু হয়।

অ্যালগরিদমটি অত্যন্ত সরল হয়ে যায়। যদিও প্রতিটি ইটারেশনে সাধারণ অ্যালগরিদম চালানো হয়, আমরা উল্লেখযোগ্য অগ্রগতি অর্জন করেছি – একটি লিনিয়ার সময়ে চলা অ্যালগরিদম পেয়েছি। পরে আমরা প্রমাণ করব যে রানিং টাইম লিনিয়ার।

ইমপ্লিমেন্টেশন#

ইমপ্লিমেন্টেশনটি বেশ সংক্ষিপ্ত:

vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

এই ইমপ্লিমেন্টেশন সম্পর্কে মন্তব্য#

সম্পূর্ণ সমাধানটি একটি ফাংশন হিসেবে দেওয়া হয়েছে যা $n$ দৈর্ঘ্যের একটি অ্যারে রিটার্ন করে – $s$-এর জেড-ফাংশন।

$z$ অ্যারেটি প্রাথমিকভাবে শূন্য দিয়ে পূরণ করা হয়। বর্তমান সবচেয়ে ডানদিকের ম্যাচ সেগমেন্ট $[0; 0)$ ধরা হয় (অর্থাৎ, ইচ্ছাকৃতভাবে একটি ছোট সেগমেন্ট যেটিতে কোনো $i$ নেই)।

লুপের ভিতরে $i = 1 \dots n - 1$-এর জন্য আমরা প্রথমে $z[i]$-এর প্রাথমিক মান নির্ধারণ করি – এটি হয় শূন্য থাকবে অথবা উপরের সূত্র ব্যবহার করে গণনা করা হবে।

এরপর, সাধারণ অ্যালগরিদম $z[i]$-এর মান যতটা সম্ভব বাড়ানোর চেষ্টা করে।

শেষে, যদি প্রয়োজন হয় (অর্থাৎ, যদি $i + z[i] > r$ হয়), আমরা সবচেয়ে ডানদিকের ম্যাচ সেগমেন্ট $[l, r)$ আপডেট করি।

অ্যালগরিদমের অ্যাসিম্পটোটিক আচরণ#

আমরা প্রমাণ করব যে উপরের অ্যালগরিদমের রানিং টাইম স্ট্রিংয়ের দৈর্ঘ্যের সাপেক্ষে লিনিয়ার – অর্থাৎ, এটি $O(n)$।

প্রমাণটি অত্যন্ত সরল।

আমরা নেস্টেড while লুপটিতে আগ্রহী, কারণ বাকি সবকিছু ধ্রুবক অপারেশনের সমষ্টি যার যোগফল $O(n)$।

আমরা দেখাব যে while লুপের প্রতিটি ইটারেশন ম্যাচ সেগমেন্টের ডান সীমানা $r$ বাড়াবে।

এটি করার জন্য, আমরা অ্যালগরিদমের উভয় শাখা বিবেচনা করব:

$i \geq r$
এক্ষেত্রে, হয় while লুপ কোনো ইটারেশন করবে না (যদি $s[0] \ne s[i]$ হয়), অথবা কয়েকটি ইটারেশন করবে, $i$ পজিশন থেকে শুরু করে প্রতিবার একটি ক্যারেক্টার ডানে সরে যাবে। এরপর, ডান সীমানা $r$ অবশ্যই আপডেট হবে।
তাহলে আমরা দেখেছি যে, যখন $i \geq r$, while লুপের প্রতিটি ইটারেশন নতুন $r$ ইনডেক্সের মান বাড়ায়।
$i < r$
এক্ষেত্রে, আমরা $z[i]$-কে উপরের সূত্র দ্বারা প্রদত্ত একটি নির্দিষ্ট মান $z_0$ দিয়ে ইনিশিয়ালাইজ করি। এই প্রাথমিক মান $z_0$-কে $r - i$ মানের সাথে তুলনা করা যাক। তিনটি কেস হবে:
- $z_0 < r - i$
  আমরা প্রমাণ করব যে এক্ষেত্রে while লুপের কোনো ইটারেশন হবে না।
  এটি প্রমাণ করা সহজ, যেমন পরস্পরবিরোধিতা দ্বারা: যদি while লুপ অন্তত একটি ইটারেশন করত, তাহলে এর অর্থ হতো প্রাথমিক আনুমানিক মান $z[i] = z_0$ ভুল ছিল (ম্যাচের প্রকৃত দৈর্ঘ্যের চেয়ে কম)। কিন্তু যেহেতু $s[l \dots r)$ এবং $s[0 \dots r-l)$ একই, এটি বোঝাত যে $z[i-l]$ ভুল মান ধারণ করে (যা হওয়া উচিত তার চেয়ে কম)।
  সুতরাং, যেহেতু $z[i-l]$ সঠিক এবং এটি $r - i$-এর চেয়ে কম, তাই এই মানটি প্রয়োজনীয় $z[i]$ মানের সাথে মিলে যায়।
- $z_0 = r - i$
  এক্ষেত্রে, while লুপ কয়েকটি ইটারেশন করতে পারে, কিন্তু প্রতিটি $r$ ইনডেক্সের মান বাড়াবে কারণ আমরা $s[r]$ থেকে তুলনা শুরু করব, যা $[l, r)$ ইন্টারভালের বাইরে চলে যাবে।
- $z_0 > r - i$
  $z_0$-এর সংজ্ঞা অনুসারে এই অপশনটি অসম্ভব।

তাহলে, আমরা প্রমাণ করেছি যে ভিতরের লুপের প্রতিটি ইটারেশন $r$ পয়েন্টারকে ডানদিকে এগিয়ে নেয়। যেহেতু $r$, $n-1$-এর বেশি হতে পারে না, এর অর্থ হলো ভিতরের লুপ $n-1$টির বেশি ইটারেশন করবে না।

যেহেতু অ্যালগরিদমের বাকি অংশ স্পষ্টতই $O(n)$-এ কাজ করে, আমরা প্রমাণ করলাম যে জেড-ফাংশন গণনার সম্পূর্ণ অ্যালগরিদম লিনিয়ার সময়ে চলে।

অ্যাপ্লিকেশন#

এখন আমরা নির্দিষ্ট কাজের জন্য জেড-ফাংশনের কিছু ব্যবহার বিবেচনা করব।

এই অ্যাপ্লিকেশনগুলো মূলত প্রিফিক্স ফাংশন-এর অ্যাপ্লিকেশনগুলোর সাথে অনেকটা সাদৃশ্যপূর্ণ হবে।

সাবস্ট্রিং সার্চ#

বিভ্রান্তি এড়াতে, আমরা $t$-কে টেক্সট স্ট্রিং এবং $p$-কে প্যাটার্ন বলব। সমস্যাটি হলো: টেক্সট $t$-এর মধ্যে প্যাটার্ন $p$-এর সব অবস্থান খুঁজে বের করা।

এই সমস্যা সমাধানের জন্য, আমরা একটি নতুন স্ট্রিং $s = p + \diamond + t$ তৈরি করি, অর্থাৎ $p$ এবং $t$-এর স্ট্রিং কনক্যাটেনেশন করি কিন্তু মাঝখানে একটি সেপারেটর ক্যারেক্টার $\diamond$ রাখি (আমরা $\diamond$ এমনভাবে বেছে নেব যাতে এটি $p$ বা $t$ স্ট্রিংয়ের কোথাও অবশ্যই উপস্থিত না থাকে)।

$s$-এর জন্য জেড-ফাংশন গণনা করি। তাহলে, $[0; \; \operatorname{length}(t) - 1]$ ইন্টারভালের যেকোনো $i$-এর জন্য, আমরা সংশ্লিষ্ট মান $k = z[i + \operatorname{length}(p) + 1]$ বিবেচনা করব। যদি $k$, $\operatorname{length}(p)$-এর সমান হয় তাহলে আমরা জানব $t$-এর $i$-তম পজিশনে $p$-এর একটি অবস্থান আছে, অন্যথায় $t$-এর $i$-তম পজিশনে $p$-এর কোনো অবস্থান নেই।

রানিং টাইম (এবং মেমোরি খরচ) $O(\operatorname{length}(t) + \operatorname{length}(p))$।

একটি স্ট্রিংয়ে স্বতন্ত্র সাবস্ট্রিংয়ের সংখ্যা#

$n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে, $s$-এর স্বতন্ত্র সাবস্ট্রিংয়ের সংখ্যা গণনা করুন।

আমরা এই সমস্যাটি ইটারেটিভভাবে সমাধান করব। অর্থাৎ: বর্তমানে ভিন্ন সাবস্ট্রিংয়ের সংখ্যা জানা থাকলে, $s$-এর শেষে একটি ক্যারেক্টার যোগ করার পর এই পরিমাণ পুনরায় গণনা করব।

ধরা যাক, $k$ হলো $s$-এর বর্তমান স্বতন্ত্র সাবস্ট্রিংয়ের সংখ্যা। আমরা $s$-এ একটি নতুন ক্যারেক্টার $c$ যোগ করি। স্পষ্টতই, এই নতুন ক্যারেক্টার $c$-তে শেষ হওয়া কিছু নতুন সাবস্ট্রিং থাকতে পারে (বিশেষত, সেই সব স্ট্রিং যেগুলো এই প্রতীকে শেষ হয় এবং যেগুলো আমরা আগে পাইনি)।

একটি স্ট্রিং $t = s + c$ নিন এবং এটিকে উল্টে দিন (এর ক্যারেক্টারগুলো বিপরীত ক্রমে লিখুন)। আমাদের কাজ হলো এখন $t$-এর কতগুলো প্রিফিক্স $t$-এর অন্য কোথাও পাওয়া যায় না তা গণনা করা। $t$-এর জেড-ফাংশন গণনা করি এবং এর সর্বোচ্চ মান $z_{max}$ বের করি। স্পষ্টতই, $z_{max}$ দৈর্ঘ্যের $t$-এর প্রিফিক্সটি $t$-এর মাঝখানেও কোথাও পাওয়া যায়। স্পষ্টতই, এর চেয়ে ছোট প্রিফিক্সগুলোও পাওয়া যায়।

তাহলে, আমরা দেখেছি যে $s$-এ $c$ প্রতীক যোগ করলে যে নতুন সাবস্ট্রিংগুলো আসে তাদের সংখ্যা হলো $\operatorname{length}(t) - z_{max}$।

ফলত, $n$ দৈর্ঘ্যের স্ট্রিংয়ের জন্য এই সমাধানের রানিং টাইম হলো $O(n^2)$।

উল্লেখযোগ্য যে, ঠিক একইভাবে আমরা $O(n)$ সময়ে স্বতন্ত্র সাবস্ট্রিংয়ের সংখ্যা পুনরায় গণনা করতে পারি যখন স্ট্রিংয়ের শুরুতে একটি ক্যারেক্টার যোগ করা হয়, সেইসাথে যখন এটি সরানো হয় (শেষ থেকে বা শুরু থেকে)।

স্ট্রিং কম্প্রেশন#

$n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে। এর সবচেয়ে ছোট “সংকুচিত” রূপ খুঁজে বের করুন, অর্থাৎ: সবচেয়ে কম দৈর্ঘ্যের এমন একটি স্ট্রিং $t$ খুঁজুন যাতে $s$-কে $t$-এর এক বা একাধিক কপির কনক্যাটেনেশন হিসেবে উপস্থাপন করা যায়।

সমাধান হলো: $s$-এর জেড-ফাংশন গণনা করুন, সব $i$ যেখানে $i$, $n$-কে ভাগ করে সেগুলোর মধ্য দিয়ে লুপ করুন। প্রথম যে $i$-তে $i + z[i] = n$ হয় সেখানে থামুন। তাহলে, স্ট্রিং $s$-কে $i$ দৈর্ঘ্যে সংকুচিত করা যাবে।

এই তথ্যের প্রমাণটি প্রিফিক্স ফাংশন ব্যবহার করা সমাধানের মতোই।