অভিধানগতভাবে ন্যূনতম স্ট্রিং ঘূর্ণন

আসুন বিবেচনা করা যাক একটি স্ট্রিং দেওয়া হয়েছে, আমরা জানি যে স্ট্রিংটি অক্ষরের একটি ক্রম। লেক্সিকোগ্রাফিক্যাল ঘূর্ণন হল স্ট্রিং এর ঘূর্ণন, যাতে অক্ষরকে অভিধানের ক্রমে রূপান্তর করা হয়।

সমাধানটি সহজ, আমরা কেবল প্রদত্ত স্ট্রিংটিকে নিজের সাথে সংযুক্ত করি, তারপর অন্য অ্যারেতে, সমস্ত স্ট্রিংগুলির ঘূর্ণন সংরক্ষণ করা হয়। এর পরে অ্যারেটিকে আরোহী ক্রমে সাজান, সর্বনিম্ন মান হল চূড়ান্ত ফলাফল।

ইনপুট এবং আউটপুট

Input:
The String “BCAAFAABCD”
Output:
Rotated String: “AABCDBCAAF”

অ্যালগরিদম

minStrRotation(str)

ইনপুট −৷ প্রদত্ত স্ট্রিং।

আউটপুট − ন্যূনতম স্ট্রিং রোটেশন প্রয়োজন।

Begin
   n := length of str
   define strArr to store all rotations
   tempStr := concatenate str with str again

   for i := 0 to n, do
      strArr[i] := substring of tempStr from (i to n)
   done

   sort the strArr
   return strArr[0]
End

উদাহরণ

#include <iostream>
#include <algorithm>
using namespace std;

string minStrRotation(string str) {
   int n = str.size();
   string strArray[n];    //array to store all rotations of str
   string tempStr = str + str;    //concatinate str two times

   for (int i = 0; i < n; i++)
      strArray[i] = tempStr.substr(i, n);    //get sub string from ith index to nth index
   sort(strArray, strArray+n);
   return strArray[0];    //The first index is the result
}

int main() {
   string str;
   cout << "Enter String: "; cin >> str;
   cout << "Rotated String: " << minStrRotation(str);
}

আউটপুট

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF