রিপিটিশন (Repetition) খোঁজা#
$n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে।
একটি রিপিটিশন হলো পরপর দুটি অভিন্ন স্ট্রিং-এর উপস্থিতি। অন্য কথায়, একটি রিপিটিশন ইনডেক্সের এমন একটি জোড়া $i < j$ দ্বারা বর্ণনা করা যায় যেন সাবস্ট্রিং $s[i \dots j]$ পরপর লেখা দুটি অভিন্ন স্ট্রিং দিয়ে গঠিত।
চ্যালেঞ্জ হলো একটা দেওয়া স্ট্রিং $s$-এ সকল রিপিটিশন খুঁজে বের করা। অথবা একটি সরলীকৃত কাজ: যেকোনো রিপিটিশন খোঁজো বা দীর্ঘতম রিপিটিশন খোঁজো।
এখানে বর্ণিত অ্যালগরিদমটি ১৯৮২ সালে মেইন এবং লোরেন্টজ প্রকাশ করেন।
উদাহরণ#
নিচের উদাহরণ স্ট্রিং-এ রিপিটিশনগুলো দেখো:
$$acababaee$$স্ট্রিংটিতে নিচের তিনটি রিপিটিশন আছে:
- $s[2 \dots 5] = abab$
- $s[3 \dots 6] = baba$
- $s[7 \dots 8] = ee$
আরেকটি উদাহরণ:
$$abaaba$$এখানে শুধু দুটি রিপিটিশন আছে
- $s[0 \dots 5] = abaaba$
- $s[2 \dots 3] = aa$
রিপিটিশনর সংখ্যা#
সাধারণভাবে $n$ দৈর্ঘ্যের একটি স্ট্রিং-এ $O(n^2)$ পর্যন্ত রিপিটিশন থাকতে পারে। একটি স্পষ্ট উদাহরণ হলো $n$ বার একই অক্ষর দিয়ে গঠিত স্ট্রিং, এই ক্ষেত্রে জোড় দৈর্ঘ্যের যেকোনো সাবস্ট্রিং একটি রিপিটিশন। সাধারণভাবে ছোট পিরিয়ডের যেকোনো পিরিয়ডিক স্ট্রিং-এ অনেক রিপিটিশন থাকবে।
অন্যদিকে এই তথ্যটি রিপিটিশনর সংখ্যা $O(n \log n)$ সময়ে গণনা করতে বাধা দেয় না, কারণ অ্যালগরিদম সংকুচিত আকারে, একসাথে কয়েকটি করে গ্রুপে রিপিটিশন দিতে পারে।
এমনকি এমন ধারণাও আছে, যা পিরিয়ডিক সাবস্ট্রিং-এর গ্রুপগুলোকে চারটি আকারের টাপল দিয়ে বর্ণনা করে। প্রুফিত হয়েছে যে এরকম গ্রুপের সংখ্যা স্ট্রিং দৈর্ঘ্যের সাপেক্ষে সর্বাধিক লিনিয়ার।
এছাড়া, রিপিটিশনর সংখ্যা সম্পর্কিত আরও কিছু আকর্ষণীয় ফলাফল:
প্রিমিটিভ রিপিটিশনর সংখ্যা (যেগুলোর অর্ধেক আবার রিপিটিশন নয়) সর্বাধিক $O(n \log n)$।
যদি আমরা রিপিটিশনগুলোকে সংখ্যার টাপল (ক্রোশেমোর ট্রিপল বলা হয়) $(i,~ p,~ r)$ দিয়ে এনকোড করি (যেখানে $i$ শুরুর অবস্থান, $p$ পুনরাবৃত্ত সাবস্ট্রিং-এর দৈর্ঘ্য, এবং $r$ রিপিটিশনর সংখ্যা), তাহলে সকল রিপিটিশন $O(n \log n)$ এরকম ট্রিপল দিয়ে বর্ণনা করা যায়।
ফিবোনাচি স্ট্রিং, যা এভাবে ডিফাইন করা
\[\begin{align} t_0 &= a, \\\\ t_1 &= b, \\\\ t_i &= t_{i-1} + t_{i-2}, \end{align}\]“দৃঢ়ভাবে” পিরিয়ডিক। ফিবোনাচি স্ট্রিং $f_i$-তে রিপিটিশনর সংখ্যা, এমনকি ক্রোশেমোর ট্রিপলে সংকুচিত করলেও, $O(f_n \log f_n)$। প্রিমিটিভ রিপিটিশনর সংখ্যাও $O(f_n \log f_n)$।
মেইন-লোরেন্টজ অ্যালগরিদম#
মেইন-লোরেন্টজ অ্যালগরিদমের পেছনের ধারণা হলো ডিভাইড অ্যান্ড কনকার।
এটা প্রাথমিক স্ট্রিংকে দুই ভাগে ভাগ করে, এবং দুটি রিকার্সিভ কলের মাধ্যমে প্রতিটি অর্ধে সম্পূর্ণ থাকা রিপিটিশনর সংখ্যা গণনা করে। এরপর আসে কঠিন অংশ। অ্যালগরিদম প্রথম অর্ধে শুরু হয়ে দ্বিতীয় অর্ধে শেষ হওয়া সকল রিপিটিশন খুঁজে বের করে (যাদেরকে আমরা ক্রসিং রিপিটিশন বলব)। এটা মেইন-লোরেন্টজ অ্যালগরিদমের মূল অংশ, এবং আমরা এটা এখানে বিস্তারিত আলোচনা করব।
ডিভাইড অ্যান্ড কনকার অ্যালগরিদমের কমপ্লেক্সিটি ভালোভাবে গবেষণা করা হয়েছে। মাস্টার থিওরেম বলে, আমরা একটি $O(n \log n)$ অ্যালগরিদম পাব, যদি আমরা ক্রসিং রিপিটিশন $O(n)$ সময়ে গণনা করতে পারি।
ক্রসিং রিপিটিশন খোঁজা#
তাই আমরা এমন সকল রিপিটিশন খুঁজতে চাই যেগুলো স্ট্রিং-এর প্রথম অর্ধে শুরু হয়, যাকে $u$ বলি, এবং দ্বিতীয় অর্ধে শেষ হয়, যাকে $v$ বলি:
$$s = u + v$$তাদের দৈর্ঘ্য প্রায় $s$-এর দৈর্ঘ্যের অর্ধেকের সমান।
একটি নির্বিচার রিপিটিশন কনসিডার করো এবং মাঝের অক্ষরটি দেখো (সোজা কথায় রিপিটিশনর দ্বিতীয় অর্ধের প্রথম অক্ষর)। অর্থাৎ যদি রিপিটিশনটি সাবস্ট্রিং $s[i \dots j]$ হয়, তাহলে মাঝের অক্ষর হলো $(i + j + 1) / 2$।
আমরা একটি রিপিটিশনকে বাম বা ডান বলি এই অক্ষরটি কোন স্ট্রিং-এ আছে তার উপর নির্ভর করে - স্ট্রিং $u$-তে নাকি স্ট্রিং $v$-তে। অন্য কথায়, একটি স্ট্রিংকে বাম বলা হয়, যদি এর অধিকাংশ $u$-তে থাকে, অন্যথায় আমরা একে ডান বলি।
আমরা এখন আলোচনা করব কিভাবে সকল বাম রিপিটিশন খুঁজতে হয়। সকল ডান রিপিটিশন একইভাবে পাওয়া যায়।
বাম রিপিটিশনর দৈর্ঘ্যকে $2l$ দিয়ে চিহ্নিত করি (অর্থাৎ রিপিটিশনর প্রতিটি অর্ধের দৈর্ঘ্য $l$)। স্ট্রিং $v$-তে পড়া রিপিটিশনর প্রথম অক্ষরটি কনসিডার করো (এটা স্ট্রিং $s$-এ $|u|$ অবস্থানে আছে)। এটা $l$ অবস্থান আগের অক্ষরের সাথে মিলে, এই অবস্থানকে $cntr$ বলি।
আমরা এই $cntr$ অবস্থানটি ফিক্স করব, এবং এই $cntr$ অবস্থানের সকল রিপিটিশন খুঁজব।
উদাহরণস্বরূপ:
$$c ~ \underset{cntr}{a} ~ c ~ | ~ a ~ d ~ a$$উল্লম্ব রেখাটি দুটি অর্ধকে ভাগ করে। এখানে আমরা $cntr = 1$ অবস্থান ফিক্স করেছি, এবং এই অবস্থানে আমরা রিপিটিশন $caca$ পাই।
এটা স্পষ্ট যে, যদি আমরা $cntr$ অবস্থান ফিক্স করি, আমরা একই সাথে সম্ভাব্য রিপিটিশনর দৈর্ঘ্যও ফিক্স করি: $l = |u| - cntr$। একবার আমরা জানি কিভাবে এই রিপিটিশনগুলো খুঁজতে হয়, আমরা $cntr$-এর সকল সম্ভাব্য মান $0$ থেকে $|u|-1$ পর্যন্ত ইটারেট করব, এবং $l = |u|,~ |u|-1,~ \dots, 1$ দৈর্ঘ্যের সকল বাম ক্রসওভার রিপিটিশন খুঁজব।
বাম ক্রসিং রিপিটিশনর শর্ত#
এখন, একটি ফিক্সড $cntr$-এর জন্য কিভাবে সকল রিপিটিশন খুঁজব? মনে রাখো এরকম একাধিক রিপিটিশন থাকতে পারে।
চলো আবার একটি ভিজুয়ালাইজেশন দেখি, এবার রিপিটিশন $abcabc$-এর জন্য:
$$\overbrace{a}^{l_1} ~ \overbrace{\underset{cntr}{b} ~ c}^{l_2} ~ \overbrace{a}^{l_1} ~ | ~ \overbrace{b ~ c}^{l_2}$$এখানে আমরা রিপিটিশনর দুটি খণ্ডের দৈর্ঘ্যকে $l_1$ এবং $l_2$ দিয়ে চিহ্নিত করেছি: $l_1$ হলো $cntr-1$ অবস্থান পর্যন্ত রিপিটিশনর দৈর্ঘ্য, এবং $l_2$ হলো $cntr$ থেকে রিপিটিশনর অর্ধের শেষ পর্যন্ত দৈর্ঘ্য। রিপিটিশনর মোট দৈর্ঘ্য $2l = l_1 + l_2 + l_1 + l_2$।
$cntr$ অবস্থানে $2l = 2(l_1 + l_2) = 2(|u| - cntr)$ দৈর্ঘ্যের এরকম রিপিটিশনর জন্য প্রয়োজনীয় ও পর্যাপ্ত শর্ত তৈরি করা যাক:
- $k_1$ হলো সেই সর্ববৃহৎ সংখ্যা যেন $cntr$ অবস্থানের আগের প্রথম $k_1$ অক্ষর স্ট্রিং $u$-এর শেষ $k_1$ অক্ষরের সাথে মিলে:
- $k_2$ হলো সেই সর্ববৃহৎ সংখ্যা যেন $cntr$ অবস্থান থেকে শুরু হওয়া $k_2$ অক্ষর স্ট্রিং $v$-এর প্রথম $k_2$ অক্ষরের সাথে মিলে:
- তাহলে যেকোনো জোড়া $(l_1,~ l_2)$ এর জন্য ঠিক তখনই রিপিটিশন আছে যখন
সারসংক্ষেপ:
- আমরা একটি নির্দিষ্ট $cntr$ অবস্থান ফিক্স করি।
- আমরা এখন যে সকল রিপিটিশন খুঁজব তাদের দৈর্ঘ্য $2l = 2(|u| - cntr)$। একাধিক এরকম রিপিটিশন থাকতে পারে, তারা $l_1$ এবং $l_2 = l - l_1$ দৈর্ঘ্যের উপর নির্ভর করে।
- আমরা উপরে বর্ণিত অনুযায়ী $k_1$ এবং $k_2$ খুঁজি।
- তাহলে সকল উপযুক্ত রিপিটিশন হলো সেগুলো যেখানে খণ্ড $l_1$ এবং $l_2$-এর দৈর্ঘ্য নিচের শর্ত পূরণ করে:
তাই একমাত্র অবশিষ্ট অংশ হলো কিভাবে আমরা প্রতিটি $cntr$ অবস্থানের জন্য দ্রুত $k_1$ এবং $k_2$ মান গণনা করতে পারি। ভালো খবর হলো আমরা Z-ফাংশন ব্যবহার করে $O(1)$-এ এগুলো গণনা করতে পারি:
- প্রতিটি অবস্থানের জন্য $k_1$ মান খুঁজতে আমরা $\overline{u}$ স্ট্রিং-এর (অর্থাৎ বিপরীত স্ট্রিং $u$) Z-ফাংশন গণনা করি। তাহলে একটি নির্দিষ্ট $cntr$-এর জন্য $k_1$ মান Z-ফাংশন অ্যারের সংশ্লিষ্ট মানের সমান হবে।
- সকল $k_2$ মান আগে থেকে গণনা করতে আমরা $v + \# + u$ স্ট্রিং-এর (অর্থাৎ সেপারেটর অক্ষর $\#$ সহ $u$ এবং $v$ জোড়া) Z-ফাংশন গণনা করি। আবার $k_2$ মান পেতে আমাদের শুধু Z-ফাংশনের সংশ্লিষ্ট মান দেখতে হবে।
তাই এটা সকল বাম ক্রসিং রিপিটিশন খুঁজে পেতে যথেষ্ট।
ডান ক্রসিং রিপিটিশন#
ডান ক্রসিং রিপিটিশন গণনার জন্য আমরা একইভাবে কাজ করি: আমরা কেন্দ্র $cntr$-কে স্ট্রিং $u$-এর শেষ অক্ষরের সাথে সম্পর্কিত অক্ষর হিসেবে ডিফাইন করি।
তাহলে $k_1$ দৈর্ঘ্যকে $cntr$ অবস্থানের আগে (সহ) সবচেয়ে বেশি সংখ্যক অক্ষর হিসেবে ডিফাইন করা হবে যেগুলো স্ট্রিং $u$-এর শেষ অক্ষরগুলোর সাথে মিলে। এবং $k_2$ দৈর্ঘ্যকে $cntr + 1$ থেকে শুরু হওয়া সবচেয়ে বেশি সংখ্যক অক্ষর হিসেবে ডিফাইন করা হবে যেগুলো স্ট্রিং $v$-এর অক্ষরগুলোর সাথে মিলে।
তাই আমরা $\overline{u} + \# + \overline{v}$ এবং $v$ স্ট্রিং-এর Z-ফাংশন গণনা করে $k_1$ এবং $k_2$ মান খুঁজতে পারি।
এরপর আমরা সকল $cntr$ অবস্থান দেখে রিপিটিশন খুঁজতে পারি, এবং বাম ক্রসিং রিপিটিশনর জন্য যে শর্ত ব্যবহার করেছিলাম সেই একই শর্ত ব্যবহার করতে পারি।
ইমপ্লিমেন্টেশন#
মেইন-লোরেন্টজ অ্যালগরিদমের ইমপ্লিমেন্টেশন $O(n \log n)$ সময়ে চারটি আকারের বিশেষ টাপল $(cntr,~ l,~ k_1,~ k_2)$ আকারে সকল রিপিটিশন খুঁজে বের করে। তুমি যদি শুধুমাত্র একটি স্ট্রিং-এ রিপিটিশনর সংখ্যা খুঁজতে চাও, বা শুধুমাত্র দীর্ঘতম রিপিটিশন খুঁজতে চাও, তাহলে এই তথ্যই যথেষ্ট এবং রানটাইম $O(n \log n)$ থাকবে।
লক্ষ্য করো যদি তুমি এই টাপলগুলো প্রসারিত করে প্রতিটি রিপিটিশনর শুরু এবং শেষ অবস্থান পেতে চাও, তাহলে রানটাইম $O(n^2)$ হবে (মনে রাখো $O(n^2)$ রিপিটিশন থাকতে পারে)। এই ইমপ্লিমেন্টেশনে আমরা তাই করব, এবং সকল পাওয়া রিপিটিশন শুরু এবং শেষ ইনডেক্সের জোড়ার ভেক্টরে সংরক্ষণ করব।
vector<int> z_function(string const& s) {
int n = s.size();
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;
}
int get_z(vector<int> const& z, int i) {
if (0 <= i && i < (int)z.size())
return z[i];
else
return 0;
}
vector<pair<int, int>> repetitions;
void convert_to_repetitions(int shift, bool left, int cntr, int l, int k1, int k2) {
for (int l1 = max(1, l - k2); l1 <= min(l, k1); l1++) {
if (left && l1 == l) break;
int l2 = l - l1;
int pos = shift + (left ? cntr - l1 : cntr - l - l1 + 1);
repetitions.emplace_back(pos, pos + 2*l - 1);
}
}
void find_repetitions(string s, int shift = 0) {
int n = s.size();
if (n == 1)
return;
int nu = n / 2;
int nv = n - nu;
string u = s.substr(0, nu);
string v = s.substr(nu);
string ru(u.rbegin(), u.rend());
string rv(v.rbegin(), v.rend());
find_repetitions(u, shift);
find_repetitions(v, shift + nu);
vector<int> z1 = z_function(ru);
vector<int> z2 = z_function(v + '#' + u);
vector<int> z3 = z_function(ru + '#' + rv);
vector<int> z4 = z_function(v);
for (int cntr = 0; cntr < n; cntr++) {
int l, k1, k2;
if (cntr < nu) {
l = nu - cntr;
k1 = get_z(z1, nu - cntr);
k2 = get_z(z2, nv + 1 + cntr);
} else {
l = cntr - nu + 1;
k1 = get_z(z3, nu + 1 + nv - 1 - (cntr - nu));
k2 = get_z(z4, (cntr - nu) + 1);
}
if (k1 + k2 >= l)
convert_to_repetitions(shift, cntr < nu, cntr, l, k1, k2);
}
}