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++程序来查找字典序最小的字符串旋转的算法和方法。