ম্যানাকারের অ্যালগরিদম - $O(N)$-এ সকল সাব-প্যালিন্ড্রোম বের করা#
সমস্যার বিবৃতি#
$n$ দৈর্ঘ্যের স্ট্রিং $s$ দেওয়া আছে। এমন সকল জোড়া $(i, j)$ বের করুন যেন সাবস্ট্রিং $s[i\dots j]$ একটি প্যালিন্ড্রোম হয়। স্ট্রিং $t$ একটি প্যালিন্ড্রোম যখন $t = t_{rev}$ ($t_{rev}$ হলো $t$-এর বিপরীত স্ট্রিং)।
আরও সুনির্দিষ্ট বিবৃতি#
ওয়ার্স্ট কেসে স্ট্রিং-এ $O(n^2)$ পর্যন্ত প্যালিন্ড্রোমিক সাবস্ট্রিং থাকতে পারে, এবং প্রথম দৃষ্টিতে মনে হয় যে এই সমস্যার কোনো লিনিয়ার অ্যালগরিদম নেই।
কিন্তু প্যালিন্ড্রোম সম্পর্কিত তথ্য সংক্ষিপ্ত আকারে রাখা যায়: প্রতিটি অবস্থান $i$-এর জন্য আমরা এই অবস্থানকে কেন্দ্র করে অশূন্য প্যালিন্ড্রোমের সংখ্যা বের করব।
একটি সাধারণ কেন্দ্র বিশিষ্ট প্যালিন্ড্রোমগুলো একটি সংলগ্ন চেইন তৈরি করে, অর্থাৎ যদি $i$-তে কেন্দ্রিত $l$ দৈর্ঘ্যের একটি প্যালিন্ড্রোম থাকে, তাহলে $i$-তে কেন্দ্রিত $l-2$, $l-4$ ইত্যাদি দৈর্ঘ্যের প্যালিন্ড্রোমও আছে। তাই, আমরা এইভাবে সকল প্যালিন্ড্রোমিক সাবস্ট্রিং-এর তথ্য সংগ্রহ করব।
বিজোড় এবং জোড় দৈর্ঘ্যের প্যালিন্ড্রোমগুলো আলাদাভাবে $d_{odd}[i]$ এবং $d_{even}[i]$ হিসেবে গণনা করা হয়। জোড় দৈর্ঘ্যের প্যালিন্ড্রোমের জন্য আমরা ধরে নিই যে সেগুলো $i$ অবস্থানে কেন্দ্রিত যদি তাদের দুটি কেন্দ্রীয় অক্ষর $s[i]$ এবং $s[i-1]$ হয়।
উদাহরণস্বরূপ, স্ট্রিং $s = abababc$-তে $s[3] = b$ অবস্থানে কেন্দ্রিত তিনটি বিজোড় দৈর্ঘ্যের প্যালিন্ড্রোম আছে, অর্থাৎ $d_{odd}[3] = 3$:
$$a\ \overbrace{b\ a\ \underbrace{b}_{s_3}\ a\ b}^{d_{odd}[3]=3} c$$এবং স্ট্রিং $s = cbaabd$-তে $s[3] = a$ অবস্থানে কেন্দ্রিত দুটি জোড় দৈর্ঘ্যের প্যালিন্ড্রোম আছে, অর্থাৎ $d_{even}[3] = 2$:
$$c\ \overbrace{b\ a\ \underbrace{a}_{s_3}\ b}^{d_{even}[3]=2} d$$এটি একটি বিস্ময়কর তথ্য যে এমন একটি অ্যালগরিদম আছে, যা যথেষ্ট সরল, এবং এই “প্যালিন্ড্রোমিটি অ্যারে” $d_{odd}[]$ এবং $d_{even}[]$ লিনিয়ার সময়ে গণনা করে। অ্যালগরিদমটি এই নিবন্ধে বর্ণনা করা হয়েছে।
সমাধান#
সাধারণভাবে, এই সমস্যার অনেক সমাধান আছে: স্ট্রিং হ্যাশিং দিয়ে এটি $O(n\cdot \log n)$-এ সমাধান করা যায়, এবং সাফিক্স ট্রি ও দ্রুত LCA দিয়ে এই সমস্যা $O(n)$-এ সমাধান করা যায়।
কিন্তু এখানে বর্ণিত পদ্ধতিটি যথেষ্ট সরল এবং সময় ও মেমোরি কমপ্লেক্সিটিতে কম লুকানো ধ্রুবক আছে। এই অ্যালগরিদমটি গ্লেন কে. ম্যানাকার ১৯৭৫ সালে আবিষ্কার করেন।
প্যালিন্ড্রোম নিয়ে কাজ করার আরেকটি আধুনিক পদ্ধতি হলো তথাকথিত প্যালিন্ড্রোমিক ট্রি, বা ইআরট্রি।
ট্রিভিয়াল অ্যালগরিদম#
অস্পষ্টতা এড়াতে আমরা সংজ্ঞায়িত করি “ট্রিভিয়াল অ্যালগরিদম” কী।
এটি সেই অ্যালগরিদম যা নিম্নলিখিতটি করে। প্রতিটি কেন্দ্র অবস্থান $i$-এর জন্য এটি যতক্ষণ সম্ভব উত্তর এক এক করে বাড়ানোর চেষ্টা করে, প্রতিবার সংশ্লিষ্ট অক্ষরের একটি জোড়া তুলনা করে।
এরকম একটি অ্যালগরিদম ধীর, এটি শুধুমাত্র $O(n^2)$-এ উত্তর গণনা করতে পারে।
ট্রিভিয়াল অ্যালগরিদমের ইমপ্লিমেন্টেশন:
vector<int> manacher_odd_trivial(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
for(int i = 1; i <= n; i++) {
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
}
return vector<int>(begin(p) + 1, end(p) - 1);
}টার্মিনাল অক্ষর $ এবং ^ স্ট্রিং-এর প্রান্তগুলো আলাদাভাবে পরিচালনা এড়াতে ব্যবহার করা হয়েছে।
ম্যানাকারের অ্যালগরিদম#
আমরা সকল বিজোড় দৈর্ঘ্যের সাব-প্যালিন্ড্রোম বের করার অ্যালগরিদম বর্ণনা করি, অর্থাৎ $d_{odd}[]$ গণনা করি।
দ্রুত গণনার জন্য আমরা সবচেয়ে ডানে পাওয়া (সাব-)প্যালিন্ড্রোমের এক্সক্লুসিভ সীমানা $(l, r)$ বজায় রাখব (অর্থাৎ বর্তমানে সবচেয়ে ডানের (সাব-)প্যালিন্ড্রোম হলো $s[l+1] s[l+2] \dots s[r-1]$)। প্রাথমিকভাবে আমরা $l = 0, r = 1$ সেট করি, যা খালি স্ট্রিং-এর সাথে সম্পর্কিত।
তাই, আমরা পরবর্তী $i$-এর জন্য $d_{odd}[i]$ গণনা করতে চাই, এবং $d_{odd}[]$-এর সকল পূর্ববর্তী মান ইতিমধ্যে গণনা করা হয়েছে। আমরা নিম্নলিখিতটি করি:
যদি $i$ বর্তমান সাব-প্যালিন্ড্রোমের বাইরে থাকে, অর্থাৎ $i \geq r$, তাহলে আমরা কেবল ট্রিভিয়াল অ্যালগরিদম চালাব।
তাই আমরা ক্রমাগত $d_{odd}[i]$ বাড়াব এবং প্রতিবার পরীক্ষা করব বর্তমান সবচেয়ে ডানের সাবস্ট্রিং $[i - d_{odd}[i]\dots i + d_{odd}[i]]$ একটি প্যালিন্ড্রোম কিনা। যখন আমরা প্রথম অমিল পাই বা $s$-এর সীমানায় পৌঁছাই, আমরা থামব। এই ক্ষেত্রে আমরা শেষ পর্যন্ত $d_{odd}[i]$ গণনা করেছি। এরপর, $(l, r)$ আপডেট করতে ভুলবেন না। $r$ এমনভাবে আপডেট করতে হবে যাতে এটি বর্তমান সবচেয়ে ডানের সাব-প্যালিন্ড্রোমের শেষ ইনডেক্স প্রতিনিধিত্ব করে।
এখন সেই ক্ষেত্রে বিবেচনা করুন যখন $i \le r$। আমরা $d_{odd}[]$-এর ইতিমধ্যে গণনাকৃত মান থেকে কিছু তথ্য বের করার চেষ্টা করব। তাই, সাব-প্যালিন্ড্রোম $(l, r)$-এ $i$-এর “আয়না” অবস্থান বের করি, অর্থাৎ আমরা $j = l + (r - i)$ অবস্থান পাব, এবং $d_{odd}[j]$-এর মান পরীক্ষা করব। যেহেতু $j$ হলো $(l+r)/2$-এর সাপেক্ষে $i$-এর প্রতিসম অবস্থান, আমরা প্রায় সবসময় $d_{odd}[i] = d_{odd}[j]$ অ্যাসাইন করতে পারি। চিত্র ($j$-কে ঘিরে প্যালিন্ড্রোম আসলে $i$-কে ঘিরে প্যালিন্ড্রোমে “কপি” হয়):
$$ \ldots\ \overbrace{ s_{l+1}\ \ldots\ \underbrace{ s_{j-d_{odd}[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_{odd}[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ s_{r-1}\ }^\text{palindrome}\ \ldots $$কিন্তু একটি জটিল ক্ষেত্র আছে যা সঠিকভাবে পরিচালনা করতে হবে: যখন “ভিতরের” প্যালিন্ড্রোম “বাইরের”-এর সীমানায় পৌঁছায়, অর্থাৎ $j - d_{odd}[j] \le l$ (বা সমতুল্যভাবে, $i + d_{odd}[j] \ge r$)। যেহেতু “বাইরের” প্যালিন্ড্রোমের বাইরে প্রতিসাম্য নিশ্চিত নয়, শুধু $d_{odd}[i] = d_{odd}[j]$ অ্যাসাইন করা ভুল হবে: আমাদের কাছে যথেষ্ট তথ্য নেই যে $i$ অবস্থানের প্যালিন্ড্রোমের দৈর্ঘ্য একই।
আসলে, এরকম পরিস্থিতি সঠিকভাবে পরিচালনা করতে আমাদের আপাতত প্যালিন্ড্রোমের দৈর্ঘ্য সীমিত করতে হবে, অর্থাৎ $d_{odd}[i] = r - i$ অ্যাসাইন করতে হবে। এরপর আমরা ট্রিভিয়াল অ্যালগরিদম চালাব যা $d_{odd}[i]$ যতটা সম্ভব বাড়ানোর চেষ্টা করবে।
এই ক্ষেত্রের চিত্র ($j$ কেন্দ্রিক প্যালিন্ড্রোম “বাইরের” প্যালিন্ড্রোমে ফিট করার জন্য সীমিত):
$$ \ldots\ \overbrace{ \underbrace{ s_{l+1}\ \ldots\ s_j\ \ldots\ s_{j+(j-l)-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)+1}\ \ldots\ s_i\ \ldots\ s_{r-1} }_\text{palindrome}\ }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try to advance here} $$চিত্রে দেখানো হয়েছে যে, যদিও $j$ কেন্দ্রিক প্যালিন্ড্রোম বড় হতে পারত এবং “বাইরের” প্যালিন্ড্রোমের বাইরে যেতে পারত, কিন্তু $i$ কেন্দ্র হিসেবে আমরা শুধু সেই অংশটুকু ব্যবহার করতে পারি যা সম্পূর্ণরূপে “বাইরের” প্যালিন্ড্রোমের মধ্যে ফিট করে। কিন্তু $i$ অবস্থানের উত্তর ($d_{odd}[i]$) এই অংশের চেয়ে অনেক বড় হতে পারে, তাই এরপর আমরা ট্রিভিয়াল অ্যালগরিদম চালাব যা “বাইরের” প্যালিন্ড্রোমের বাইরে, অর্থাৎ “এখানে এগোনোর চেষ্টা” অঞ্চলে এটি বাড়ানোর চেষ্টা করবে।
আবার, প্রতিটি $d_{odd}[i]$ গণনার পরে $(l, r)$ মান আপডেট করতে ভুলবেন না।
ম্যানাকারের অ্যালগরিদমের কমপ্লেক্সিটি#
প্রথম দৃষ্টিতে এটি স্পষ্ট নয় যে এই অ্যালগরিদমের লিনিয়ার টাইম কমপ্লেক্সিটি আছে, কারণ একটি নির্দিষ্ট অবস্থানের উত্তর খোঁজার সময় আমরা প্রায়ই নেইভ অ্যালগরিদম চালাই।
তবে, আরও সতর্ক বিশ্লেষণে দেখা যায় যে অ্যালগরিদমটি লিনিয়ার। আসলে, Z-ফাংশন তৈরির অ্যালগরিদম, যা এই অ্যালগরিদমের মতো দেখায়, সেটিও লিনিয়ার সময়ে কাজ করে।
আমরা লক্ষ্য করতে পারি যে ট্রিভিয়াল অ্যালগরিদমের প্রতিটি ইটারেশন $r$-কে এক বাড়ায়। এছাড়া অ্যালগরিদম চলাকালীন $r$ কখনো কমে না। তাই, ট্রিভিয়াল অ্যালগরিদম মোট $O(n)$ ইটারেশন করবে।
ম্যানাকারের অ্যালগরিদমের অন্যান্য অংশ স্পষ্টতই লিনিয়ার সময়ে কাজ করে। এভাবে, আমরা $O(n)$ টাইম কমপ্লেক্সিটি পাই।
ম্যানাকারের অ্যালগরিদমের ইমপ্লিমেন্টেশন#
$d_{odd}[]$ গণনার জন্য, আমরা নিম্নলিখিত কোড পাই। লক্ষণীয় বিষয়গুলো:
- $i$ হলো বর্তমান প্যালিন্ড্রোমের কেন্দ্র অক্ষরের ইনডেক্স।
- যদি $i$, $r$-কে অতিক্রম করে, $d_{odd}[i]$ ০ দিয়ে ইনিশিয়ালাইজ হয়।
- যদি $i$, $r$-কে অতিক্রম না করে, $d_{odd}[i]$ হয় $d_{odd}[j]$ দিয়ে ইনিশিয়ালাইজ হয়, যেখানে $j$ হলো $(l,r)$-এ $i$-এর আয়না অবস্থান, অথবা $d_{odd}[i]$ “বাইরের” প্যালিন্ড্রোমের আকারে সীমিত হয়।
- while লুপটি ট্রিভিয়াল অ্যালগরিদম নির্দেশ করে। $k$-এর মান নির্বিশেষে আমরা এটি চালাই।
- যদি $i$-তে কেন্দ্রিত প্যালিন্ড্রোমের আকার $x$ হয়, তাহলে $d_{odd}[i]$-তে $\frac{x+1}{2}$ সংরক্ষিত থাকে।
vector<int> manacher_odd(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
int l = 0, r = 1;
for(int i = 1; i <= n; i++) {
p[i] = min(r - i, p[l + (r - i)]);
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
if(i + p[i] > r) {
l = i - p[i], r = i + p[i];
}
}
return vector<int>(begin(p) + 1, end(p) - 1);
}প্যারিটি নিয়ে কাজ করা#
যদিও ম্যানাকারের অ্যালগরিদম বিজোড় এবং জোড় দৈর্ঘ্যের জন্য আলাদাভাবে ইমপ্লিমেন্ট করা সম্ভব, জোড় দৈর্ঘ্যের সংস্করণের ইমপ্লিমেন্টেশন প্রায়ই বেশি কঠিন বলে মনে করা হয়, কারণ এটি কম স্বাভাবিক এবং সহজেই অফ-বাই-ওয়ান ত্রুটি ঘটায়।
এটি প্রশমিত করতে, পুরো সমস্যাটিকে শুধুমাত্র বিজোড় দৈর্ঘ্যের প্যালিন্ড্রোমের ক্ষেত্রে রিডিউস করা সম্ভব। এর জন্য, আমরা স্ট্রিং-এর প্রতিটি অক্ষরের মাঝে এবং শুরু ও শেষে একটি অতিরিক্ত # অক্ষর রাখতে পারি:
আপনি দেখতে পাচ্ছেন, $d[2i]=2 d_{even}[i]+1$ এবং $d[2i+1]=2 d_{odd}[i]$ যেখানে $d$ হলো #-যুক্ত স্ট্রিং-এ বিজোড়-দৈর্ঘ্যের প্যালিন্ড্রোমের জন্য ম্যানাকার অ্যারে, আর $d_{odd}$ এবং $d_{even}$ মূল স্ট্রিং-এ উপরে সংজ্ঞায়িত অ্যারেগুলোর সাথে সম্পর্কিত।
প্রকৃতপক্ষে, # অক্ষরগুলো বিজোড়-দৈর্ঘ্যের প্যালিন্ড্রোমগুলোকে প্রভাবিত করে না, যেগুলো এখনও মূল স্ট্রিং-এর অক্ষরগুলোতে কেন্দ্রিত, কিন্তু এখন মূল স্ট্রিং-এর জোড়-দৈর্ঘ্যের প্যালিন্ড্রোমগুলো নতুন স্ট্রিং-এ # অক্ষরে কেন্দ্রিত বিজোড়-দৈর্ঘ্যের প্যালিন্ড্রোম হয়ে যায়।
লক্ষ্য করুন $d[2i]$ এবং $d[2i+1]$ মূলত $i$-তে কেন্দ্রিত সবচেয়ে বড় বিজোড়- এবং জোড়-দৈর্ঘ্যের প্যালিন্ড্রোমের দৈর্ঘ্যের ১ বেশি।
রিডাকশনটি নিম্নলিখিতভাবে ইমপ্লিমেন্ট করা হয়:
vector<int> manacher(string s) {
string t;
for(auto c: s) {
t += string("#") + c;
}
auto res = manacher_odd(t + "#");
return vector<int>(begin(res) + 1, end(res) - 1);
}সরলতার জন্য, অ্যারেটিকে $d_{odd}$ এবং $d_{even}$-এ বিভক্ত করা এবং তাদের স্পষ্ট গণনা বাদ দেওয়া হয়েছে।