लेक्सिकोग्राफिक रूप से न्यूनतम स्ट्रिंग रोटेशन

आइए मान लें कि एक स्ट्रिंग दी गई है, हम जानते हैं कि स्ट्रिंग वर्णों का एक क्रम है। वर्णों को शब्दावली क्रम में बदलने के लिए लेक्सिकोग्राफिकल रोटेशन स्ट्रिंग का रोटेशन है।

समाधान सरल है, हम केवल दिए गए स्ट्रिंग को अपने साथ जोड़ते हैं, फिर दूसरे सरणी में, स्ट्रिंग्स के सभी रोटेशन संग्रहीत किए जाते हैं। उसके बाद सरणी को आरोही क्रम में क्रमबद्ध करें, न्यूनतम मान अंतिम परिणाम है।

इनपुट और आउटपुट

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