পুনরাবৃত্তি (রিপিটিশন) খোঁজা#
$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);
}
}