C++程序获取字典序最小的循环序列 – 2

写一个程序来查找循环数组中的字典最小值，例如对于数组BCABDADAB，字典最小值为ABBCABDAD。

输入约束条件: 1 < n < 1000

例子：

输入：GEEKSQUIZ
输出：EEKSQUIZG

输入：GFG
输出：FGG

输入：CAPABCQ
输出：ABCQCAP

在这里，我们需要找到最小旋转的起始索引，然后打印旋转。

1) 首先假设0为当前最小起始索引。
2) 循环i = 1到n-1。
  a) 对于每个i，将以i开头的序列与当前最小起始索引比较。
  b) 如果i开头序列字典上较小，则更新当前最小起始索引。

这是算法的伪代码

function findIndexForSmallestSequence(S, n):
    result = 0
    for i = 1:n-1
        if (sequence beginning at i < 
               sequence beginning at result)
            result = i
        end if
    end for
    return result

这是上述算法的实现。

// C++ program to find lexicographically 
// smallest sequence with rotations. 
#include <iostream> 
using namespace std; 

// Function to compare lexicographically 
// two sequence with different starting 
// indexes. It returns true if sequence 
// beginning with y is lexicographically 
// greater. 
bool compareSeq(char S[], int x, int y, int n) 
{ 
    for (int i = 0; i < n; i++) { 
        if (S[x] < S[y]) 
            return false; 
        else if (S[x] > S[y]) 
            return true; 
        x = (x + 1) % n; 
        y = (y + 1) % n; 
    } 
    return true; 
} 

// Function to find starting index 
// of lexicographically smallest sequence 
int smallestSequence(char S[], int n) 
{ 
    int index = 0; 
    for (int i = 1; i < n; i++) 

        // if new sequence is smaller 
        if (compareSeq(S, index, i, n)) 

            // change index of current min 
            index = i; 

    return index; 
} 

// Function to print lexicographically 
// smallest sequence 
void printSmallestSequence(char S[], int n) 
{ 
    int starting_index = smallestSequence(S, n); 
    for (int i = 0; i < n; i++) 
        cout << S[(starting_index + i) % n]; 
} 

// driver code 
int main() 
{ 
    char S[] = "DCACBCAA"; 
    int n = 8; 
    printSmallestSequence(S, n); 
    return 0; 
}

输出: