C++程式查詢字典序最小的字串旋轉

---

本文旨在實現一個C++程式來查詢字典序最小的字串旋轉。

關於字串的定義，在C語言程式設計中，字串是一組以空字元“\0”結尾的字元。C字串中的字元儲存在一個字元陣列中。C字串與字元陣列的區別在於它以獨特的字元“\0”結尾。

找到在所有可能的旋轉中具有最低字典序的字串旋轉被稱為字典序最小的字串旋轉以及字典序最小的迴圈子串。

例如，aaccaaddbb是bbaaccaadd的字典序最小的旋轉。字串允許多個字典序最小的旋轉，但它們必須全部相等。

給定一個字串，可以有多個字典序最小的旋轉，但對於大多數應用來說，它們必須全部相等。查詢字典序最小的旋轉作為規範化字串的一種方法很有用。透過這種方式規範化字串，可以進行快速的相等性檢查，如果字串反映了潛在的同構結構，例如圖。

示例1

Let the given input string be
S : CATONTHEMAT
The output obtained here is : ATCATONTHEM

示例2

Let the given input string be
S : TUTORIALSPOINT
The output obtained here is : ALSPOINTTUTORI

示例3

Let the given input string be
S : ABCABCABC
The output obtained here is : ABCABCABC

示例4

Let the given input string be
S : AAABBBCCC
The output obtained here is : AAABBBCCC

問題陳述

實現一個C++程式來查詢字典序最小的字串旋轉程式。

方法

解決這個問題並提出一個C++程式來查詢字典序最小的字串旋轉的方法如下。

這是一個簡單的解決方案。設'str'為給定的字串。

• 將'str'自身連線起來，並將結果儲存在名為'concat'的臨時字串中。

• 為了儲存“str”的所有旋轉，建立一個字串陣列。讓我們將陣列稱為'arr'。

• 透過使用索引為0、1、2和n-1的“concat”的子字串，找到“str”的每個旋轉。將旋轉放入arr[]儲存中。

• 對arr[]排序後返回arr[0]。

演算法

實現C++程式來查詢字典序最小字串旋轉的演算法如下所示

• 步驟1 - 定義一個函式來確定字典序最小的字串的旋轉

• 步驟2 - 定義一個字元陣列，其中應儲存字典序最小的字串

• 步驟3 - 將字串向左旋轉一個單位。

• 步驟4 - 如果當前旋轉是最小值，則更新結果。

• 步驟5 - 將結果作為輸出列印。

示例：C++程式

以下是上述演算法的C++程式實現，用於獲得C++程式來查詢字典序最小的字串旋轉。

在這裡，我們使用<cstring>標頭檔案，以便更可靠地監視資料及其所需的儲存空間，CString會跟蹤整個字元資料的長度。

#include <iostream>
#include <cstring>
void findLexMinRotation(char *inputStr) {
   char minRotation[100];
   strcpy(minRotation, inputStr);
   int length = strlen(inputStr);
   for (int i = 0; i < length; i++) {
      char temp = inputStr[0];
      memmove(inputStr, inputStr + 1, length - 1);
      inputStr[length - 1] = temp;
      if (strcmp(inputStr, minRotation) < 0) {
         strcpy(minRotation, inputStr);
      }
   }
   std::cout << "The result obtained from the input string " << inputStr << " is " << minRotation << std::endl;
}
int main() {
   char input[] = "TUTORIALSPOINT";
   findLexMinRotation(input);
   return 0;
}

輸出

The result obtained from the input string TUTORIALSPOINT is ALSPOINTTUTORI

結論

同樣，我們可以獲得一個C++程式來查詢字典序最小的字串旋轉。本文解決了獲得C++程式來查詢字典序最小的字串旋轉的問題。

這裡提供了C++程式設計程式碼以及實現C++程式來查詢字典序最小的字串旋轉的演算法和方法。