字符串处理 --- 最小表示法

最小表示法：
循环数组中，使用字典序最小的一个序列来表示这个数组。例如A[5] = {5, 1, 3, 2, 4}，则最小表示法为{1, 3, 2, 4,5}。

问题：
输入两组数据，这两组数据都是循环数组或者环状数组，判断这两组数据是否一致？

设两个数组分别为A[],B[]。

解决方案：
正常解题思路：使用两个for循环进行O(n * n)次判断即可

KMP方法：将A复制一份加到A后面，然后再A中查找是否存在B字符串，但KMP算法太复杂，难记忆，需要求next[]。

最小表示法，思路一：将A,B都用最小表示法表示出来，然后进行判定

最小表示法，思路二：将A，B各自复制一份加到自己后面，然后具体思路如下：

步骤一：i为A的下标，j为B的下标，k为i和j同时移动的步数，初始化i = 0, j = 0, k = 0.

步骤二：如果A[i] == B[j]，k++。如果A[i] > B[j]，i = i + k + 1。如果B[j] > A[i]，j = j + k + 1。关于为什么A[i] > B[j] 时，i = i + k + 1。

证明是这样的，因为A[i] -- > A[i + k] 肯定不为最小表示数，加入再[i, i + k]区间中，存在x是最小表示数，则在B中必然存在B[j + x - i, j + k] < A[x, i + k]。与假设矛盾。

步骤三：如果i < len && j < len && k == len，则两个数组一致，否则不一致。

算法模板：
[cpp]
/*
测试数据：
69867
76896
*/

#include <iostream>
const int nMax = 200;
char str1[nMax], str2[nMax];
char s1[nMax], s2[nMax];

int main()
{
    freopen("e://data.txt", "r", stdin);
    while(scanf("%s%s", str1, str2) != EOF)//这里处理的是字符串
    {
        bool flag = 0;
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        if(len1 != len2) printf("NO\n");//判断两个字符串是否相等
        memcpy(s1, str1, len1 * sizeof(str1[0]));//将str1复制到s1两次，结果为s1 = str1 + str1
        memcpy(s1 + len1, str1, len1 * sizeof(str1[0]));
        memcpy(s2, str2, len1 * sizeof(str2[0]));//同样s2 = str2 + str2
        memcpy(s2 + len2, str2, len1 * sizeof(str2[0]));
        for(int i = 0, j = 0, k = 0;i < len1 && j < len1 && k < len1;)
        {
            if(s1[i + k] == s2[j + k]) ++k;
            else if(s1[i + k] > s2[i + k]) i = i + k + 1, k = 0;
            else j = j + k + 1, k = 0;
            if(k == len1)
            {
                flag = 1;
                break;
            }
        }
        printf("%s\n", flag == 1 ? "YES" : "NO");
    }
}

//最小表示法的另一种运用，直接返回数组s[]中最小表示数
int getMin(char s[], int len)//s[]也可以定义为其他类型
{
    int i = 0,//i,j的初始化有区别
        j = 1,
        k = 0;
    while(i < len && j < len && k < len)//自己与自己比较，A[],B[]都是s[]数组，用i,j对应不同的下标。
    {
        int t = s[(i + k) % len] - s[(j + k) % len];//这里等效于将两个字符数组s连接起来
        if(!t)//两数组相等
            ++ k;
        else
        {
            if(t > 0)
                i += k + 1;
            else
                j += k + 1;
            if(i == j)//函数的目的是返回最小表示数，只需要保留i和j中较小的一位即可，所以出现j = j的情况，i++或者j++，继续匹配
                i ++;
        }
        k = 0;
    }
    return i < j ? i : j;//返回i,j中较小的一个
}

作者：lhshaoren

补充：软件开发 , C++ ,