การหมุนสตริงขั้นต่ำของ Lexicographically

ให้เราพิจารณาสตริงที่ให้มา เรารู้ว่าสตริงนั้นเป็นลำดับของอักขระ การหมุนพจนานุกรมคือการหมุนของสตริง เพื่อแปลงอักขระตามลำดับพจนานุกรม

วิธีแก้ปัญหานั้นง่ายมาก เราแค่เชื่อมสตริงที่กำหนดกับตัวมันเอง จากนั้นในอาร์เรย์อื่น การหมุนของสตริงทั้งหมดจะถูกเก็บไว้ หลังจากนั้นเรียงลำดับอาร์เรย์จากน้อยไปมาก ค่าต่ำสุดคือผลลัพธ์สุดท้าย

อินพุตและเอาต์พุต

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