C++ 程序查找字典顺序最小的字符串旋转

简介

在字符串算法中，有一个经典问题叫做“字符串旋转”。给定一个由小写字母组成的字符串s，我们可以把这个字符串前面的任意一段移动到字符串的最后面，从而得到一个新的字符串。例如，把字符串“abcd”从中间分开，并将其前面的一段移动到字符串的最后面，可以得到一个新的字符串“cdab”。

我们可以按照字典序对字符串的旋转进行排序，并得到排序后顺序最小的字符串旋转。如对于字符串“cdab”，可以得到字符串的四个旋转：“cdab”、“dabc”、“abcd”、“bcda”，按照字典序排序后，顺序最小的字符串旋转为“abcd”。

在本文中，我们将介绍如何使用C++编写程序，查找字典顺序最小的字符串旋转。

解题思路

对于给定的字符串s，我们需要找到其字典序最小的旋转字符串。假设字符串s的长度为n，我们可以对其进行如下操作：

定义两倍长度的新字符串s + s，这样我们就可以使用字符串的子串操作来找到所有可能的旋转字符串。
使用一个起点start，初始值为0。利用组后、子串操作求出从start开始到结束的子字符串，然后遍历字符串，查找其中字典序最小的字符串。
更新起点start的值，重复上述步骤。

这样，我们就可以查找到字典序最小的字符串旋转。

下面是基于此方法实现的C++程序：

#include <iostream>
#include <cstring>
using namespace std;

int findMinString(string s) {
    int n = s.length();
    // 定义新字符串
    string t = s + s;
    // 起始位置
    int start = 0;
    // 遍历新字符串
    for (int i = 1; i <= n; ++i) {
        int j = 0, k = i;  // j为原字符串起点，k为新字符串起点
        // 查找字典序最小的字符串
        while (j < n && k < 2 * n) {
            if (t[j] < t[k]) {
                break;
            } else if (t[j] > t[k]) {
                j = i;  // 更新起始位置
            } else {
                ++j, ++k;
            }
        }
        if (j == n) {
            return start;  // 找到字典序最小的旋转子串
        }
        start = t[j + 1] <= t[start + 1] ? j + 1 : start + 1;
    }
    return start;
}

int main() {
    // 测试样例：s="cdab"
    string s = "cdab";
    int start = findMinString(s);
    cout << s.substr(start) + s.substr(0, start) << endl; // 输出字典序最小的旋转子串
    return 0;
}

在上述代码中，我们使用了string类来操作字符串以及指针。一些注意事项如下：