লিন্ডন ফ্যাক্টরাইজেশন#
লিন্ডন ফ্যাক্টরাইজেশন#
প্রথমে লিন্ডন ফ্যাক্টরাইজেশনের ধারণাটি সংজ্ঞায়িত করা যাক।
একটি স্ট্রিংকে সিম্পল (বা লিন্ডন ওয়ার্ড) বলা হয়, যদি এটি তার নিজের যেকোনো নন-ট্রিভিয়াল সাফিক্সের চেয়ে কঠোরভাবে ছোট হয়। সিম্পল স্ট্রিং-এর উদাহরণ: $a$, $b$, $ab$, $aab$, $abb$, $ababb$, $abcd$। দেখানো যায় যে একটি স্ট্রিং সিম্পল, যদি এবং কেবল যদি এটি তার সকল নন-ট্রিভিয়াল সাইক্লিক শিফটের চেয়ে কঠোরভাবে ছোট হয়।
এরপর, একটি প্রদত্ত স্ট্রিং $s$ ধরা যাক। স্ট্রিং $s$-এর লিন্ডন ফ্যাক্টরাইজেশন হলো একটি ফ্যাক্টরাইজেশন $s = w_1 w_2 \dots w_k$, যেখানে সকল স্ট্রিং $w_i$ সিম্পল, এবং এগুলো অবনমনশীল ক্রমে আছে $w_1 \ge w_2 \ge \dots \ge w_k$।
দেখানো যায় যে, যেকোনো স্ট্রিং-এর জন্য এরকম একটি ফ্যাক্টরাইজেশন বিদ্যমান এবং এটি অনন্য।
ডুভাল অ্যালগরিদম#
ডুভাল অ্যালগরিদম $O(n)$ সময়ে এবং $O(1)$ অতিরিক্ত মেমোরি ব্যবহার করে লিন্ডন ফ্যাক্টরাইজেশন তৈরি করে।
প্রথমে আরেকটি ধারণা পরিচয় করানো যাক: একটি স্ট্রিং $t$-কে প্রি-সিম্পল বলা হয়, যদি এর আকার হয় $t = w w \dots w \overline{w}$, যেখানে $w$ একটি সিম্পল স্ট্রিং এবং $\overline{w}$ হলো $w$-এর একটি প্রিফিক্স (সম্ভবত ফাঁকা)। একটি সিম্পল স্ট্রিং প্রি-সিম্পলও।
ডুভাল অ্যালগরিদম গ্রিডি। এর সম্পাদনের যেকোনো মুহূর্তে, স্ট্রিং $s$ আসলে তিনটি স্ট্রিং-এ বিভক্ত থাকবে $s = s_1 s_2 s_3$, যেখানে $s_1$-এর লিন্ডন ফ্যাক্টরাইজেশন ইতিমধ্যে পাওয়া গেছে এবং চূড়ান্ত হয়েছে, স্ট্রিং $s_2$ প্রি-সিম্পল (এবং আমরা এতে সিম্পল স্ট্রিং-এর দৈর্ঘ্য জানি), এবং $s_3$ সম্পূর্ণ অস্পর্শিত। প্রতিটি ইটারেশনে ডুভাল অ্যালগরিদম স্ট্রিং $s_3$-এর প্রথম অক্ষর নেয় এবং স্ট্রিং $s_2$-তে এটি যুক্ত করার চেষ্টা করে। যদি $s_2$ আর প্রি-সিম্পল না থাকে, তাহলে $s_2$-এর কিছু অংশের লিন্ডন ফ্যাক্টরাইজেশন জানা হয়ে যায়, এবং সেই অংশটি $s_1$-এ যায়।
আসুন অ্যালগরিদমটি আরও বিস্তারিতভাবে বর্ণনা করি। পয়েন্টার $i$ সবসময় স্ট্রিং $s_2$-এর শুরুতে নির্দেশ করবে। বাইরের লুপটি $i < n$ থাকা পর্যন্ত চলবে। লুপের ভিতরে আমরা দুটি অতিরিক্ত পয়েন্টার ব্যবহার করি, $j$ যা $s_3$-এর শুরুতে নির্দেশ করে, এবং $k$ যা সেই বর্তমান অক্ষরে নির্দেশ করে যার সাথে আমরা তুলনা করছি। আমরা অক্ষর $s[j]$-কে স্ট্রিং $s_2$-তে যোগ করতে চাই, এর জন্য অক্ষর $s[k]$-এর সাথে তুলনা প্রয়োজন। তিনটি ভিন্ন ক্ষেত্র হতে পারে:
- $s[j] = s[k]$: এই ক্ষেত্রে, প্রতীক $s[j]$ যোগ করলে $s_2$-এর প্রি-সিম্পলিটি নষ্ট হয় না। তাই আমরা কেবল পয়েন্টার $j$ এবং $k$ বাড়াই।
- $s[j] > s[k]$: এখানে, স্ট্রিং $s_2 + s[j]$ সিম্পল হয়ে যায়। আমরা $j$ বাড়াতে পারি এবং $k$-কে $s_2$-এর শুরুতে রিসেট করতে পারি, যাতে পরবর্তী অক্ষর সিম্পল শব্দের শুরুর সাথে তুলনা করা যায়।
- $s[j] < s[k]$: স্ট্রিং $s_2 + s[j]$ আর প্রি-সিম্পল নয়। তাই আমরা প্রি-সিম্পল স্ট্রিং $s_2$-কে এর সিম্পল স্ট্রিং এবং অবশিষ্টাংশে (সম্ভবত ফাঁকা) ভাগ করব। সিম্পল স্ট্রিং-এর দৈর্ঘ্য হবে $j - k$। পরবর্তী ইটারেশনে আমরা অবশিষ্ট $s_2$ দিয়ে আবার শুরু করি।
ইমপ্লিমেন্টেশন#
এখানে আমরা ডুভাল অ্যালগরিদমের ইমপ্লিমেন্টেশন উপস্থাপন করছি, যা একটি প্রদত্ত স্ট্রিং $s$-এর কাঙ্ক্ষিত লিন্ডন ফ্যাক্টরাইজেশন রিটার্ন করবে।
vector<string> duval(string const& s) {
int n = s.size();
int i = 0;
vector<string> factorization;
while (i < n) {
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k) {
factorization.push_back(s.substr(i, j - k));
i += j - k;
}
}
return factorization;
}কমপ্লেক্সিটি#
আসুন এই অ্যালগরিদমের রানিং টাইম অনুমান করি।
বাইরের while লুপ $n$ ইটারেশনের বেশি হয় না, কারণ প্রতিটি ইটারেশনের শেষে $i$ বাড়ে। এছাড়া দ্বিতীয় ভিতরের while লুপও $O(n)$-এ চলে, কারণ এটি শুধু চূড়ান্ত ফ্যাক্টরাইজেশন আউটপুট করে।
তাই আমরা শুধু প্রথম ভিতরের while লুপ-এ আগ্রহী। ওয়ার্স্ট কেসে এটি কতগুলো ইটারেশন সম্পাদন করে? দেখা সহজ যে, বাইরের লুপের প্রতিটি ইটারেশনে আমরা যে সিম্পল শব্দগুলো চিহ্নিত করি সেগুলো অতিরিক্ত তুলনা করা অবশিষ্টাংশের চেয়ে দীর্ঘ। তাই অবশিষ্টাংশের যোগফলও $n$-এর চেয়ে ছোট হবে, যার মানে আমরা প্রথম ভিতরের while লুপের সর্বাধিক $O(n)$ ইটারেশন সম্পাদন করি। আসলে মোট অক্ষর তুলনার সংখ্যা $4n - 3$-এর বেশি হবে না।
ক্ষুদ্রতম সাইক্লিক শিফট বের করা#
একটি স্ট্রিং $s$ ধরা যাক। আমরা স্ট্রিং $s + s$-এর জন্য লিন্ডন ফ্যাক্টরাইজেশন তৈরি করি ($O(n)$ সময়ে)। আমরা ফ্যাক্টরাইজেশনে এমন একটি সিম্পল স্ট্রিং খুঁজব, যা $n$-এর চেয়ে ছোট অবস্থানে শুরু হয় (অর্থাৎ $s$-এর প্রথম ইনস্ট্যান্সে শুরু হয়), এবং $n$-এর সমান বা বেশি অবস্থানে শেষ হয় (অর্থাৎ $s$-এর দ্বিতীয় ইনস্ট্যান্সে)। বলা হয় যে, এই সিম্পল স্ট্রিং-এর শুরুর অবস্থানটি হবে কাঙ্ক্ষিত ক্ষুদ্রতম সাইক্লিক শিফটের শুরু। এটি লিন্ডন ডিকম্পোজিশনের সংজ্ঞা ব্যবহার করে সহজেই যাচাই করা যায়।
সিম্পল ব্লকের শুরু সহজেই পাওয়া যায় - শুধু বাইরের লুপের প্রতিটি ইটারেশনের শুরুতে পয়েন্টার $i$ মনে রাখুন, যা বর্তমান প্রি-সিম্পল স্ট্রিং-এর শুরু নির্দেশ করে।
তাই আমরা নিম্নলিখিত ইমপ্লিমেন্টেশন পাই:
string min_cyclic_string(string s) {
s += s;
int n = s.size();
int i = 0, ans = 0;
while (i < n / 2) {
ans = i;
int j = i + 1, k = i;
while (j < n && s[k] <= s[j]) {
if (s[k] < s[j])
k = i;
else
k++;
j++;
}
while (i <= k)
i += j - k;
}
return s.substr(ans, n / 2);
}