Xoay chuỗi tối thiểu về mặt ngôn ngữ học

Chúng ta hãy xem xét một chuỗi đã cho, chúng ta biết rằng chuỗi là một chuỗi các ký tự. Vòng quay từ vựng là sự xoay vòng của chuỗi, để chuyển đổi các ký tự theo thứ tự từ vựng.

Giải pháp rất đơn giản, chúng ta chỉ cần nối chuỗi đã cho với chính nó, sau đó trong một mảng khác, tất cả các vòng quay của chuỗi được lưu trữ. Sau đó, sắp xếp mảng theo thứ tự tăng dần, giá trị thấp nhất là kết quả cuối cùng.

Đầu vào và Đầu ra

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

Thuật toán

minStrRotation(str)

Đầu vào - Chuỗi đã cho.

Đầu ra - Yêu cầu xoay chuỗi tối thiểu.

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

Ví dụ

#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);
}

Đầu ra

Enter String: BCAAFAABCD
Rotated String: AABCDBCAAF