ধরা যাক একটি স্ট্রিং দেওয়া আছে, আমরা জানি স্ট্রিং ক্যারেক্টারের একটি ক্রম। লেক্সিকোগ্রাফিক্যাল রোটেশন হল স্ট্রিংয়ের রোটেশন, যাতে ক্যারেক্টারগুলো লেক্সিকোগ্রাফিক্যাল অর্ডারে আসে।
সমাধান সহজ, আমরা সহজে প্রদত্ত স্ট্রিংকে নিজের সাথে কনক্যাটিনেট করব, তারপর অন্য একটি অ্যারেতে স্ট্রিংয়ের সকল রোটেশন সংরক্ষণ করব। তারপর অ্যারেটি आरোহী ক্রমে সর্ট করুন, সবচেয়ে কম মানটি চূড়ান্ত ফলাফল।
ইনপুট এবং আউটপুট
ইনপুট: স্ট্রিং "BCAAFAABCD" আউটপুট: রোটেট করা স্ট্রিং: "AABCDBCAAF"
অ্যালগরিদম
minStrRotation(str)
ইনপুট - প্রদত্ত স্ট্রিং।
আউটপুট - ন্যূনতম স্ট্রিং রোটেশন প্রয়োজন।
শুরু
n := str-এর দৈর্ঘ্য
strArr সংজ্ঞায়িত করুন সকল রোটেশন সংরক্ষণে
tempStr := str কে str-এর সাথে আবার কনক্যাটিনেট করুন
i := 0 থেকে n পর্যন্ত, করুন
strArr[i] := tempStr-এর (i থেকে n) সাবস্ট্রিং
শেষ
strArr সর্ট করুন
strArr[0] ফেরত দিন
শেষউদাহরণ
#include <iostream> #include <algorithm> using namespace std; string minStrRotation(string str) { int n = str.size(); string strArray[n]; //str-এর সকল রোটেশন সংরক্ষণের অ্যারে string tempStr = str + str; //str দুবার কনক্যাটিনেট করুন for (int i = 0; i < n; i++) strArray[i] = tempStr.substr(i, n); //i-তম ইনডেক্স থেকে n-তম ইনডেক্স পর্যন্ত সাব স্ট্রিং পান sort(strArray, strArray+n); return strArray[0]; //প্রথম ইনডেক্সই ফলাফল } int main() { string str; cout << "Enter String: "; cin >> str; cout << "Rotated String: " << minStrRotation(str); }আউটপুট
Enter String: BCAAFAABCD Rotated String: AABCDBCAAF
