[C++知识库]【字符串】最小表示法

之前做的哈希算法那道雪花的题因为超时而卡了很久，最近学习了最小表示法后，先用最小表示法预处理后复杂度就降低了很多，然后就AC了，于是我来总结一下最小表示法的知识点。

概念

对于一个字符串 s， 求 s 的循环的同构字符串中字典序最小的一个字符串，即为最小表示法。

条件

给定一个字符串 s，例如"3 2 4 1 5"，求其最小表示法。

题解

可以将字符串 s 中的字符组成一个圈， 他们的顺序可以改变，但他们每个字符之间的相对顺序不能改变，因此，这题的最小表示法答案应该是"1 4 2 3 5"，而不是"1 2 3 4 5"。

思路

我们可以先把原来的字符串再抄一行，设立i， j， k 三个字母。i 指的是第一行字符串的可能最小位置， j 指的是第二行字符串的可能最小位置，而 k 则是计算连续相同的字符数量，这个区间是没有必要一次次比较的，因此 i + k 和 j + k 可以直接跳过相同字符区间，从而将算法进一步简化。当i ，j，k 三个数有一个超过字符串长度时，停止比较。最后i 和 j 两个数中较小的则为最小表示法的开始的位置。再将原来字符串翻转，然后利用同样的方法算出翻转后的字符串最小位置。最后利用两个最小位置分别得出两组可能为最小表示法的字符串，两者比较之后得出更小的即为最小表示法。

简略代码

int i, j, k，ans;
string s;
s  = "3 2 4 1 5";


i = k = 0; j = 1;

while(i < s.length() && k < s.length() && k < s.length())
{
    if (s[(i + k) % s.length()] == s[(j + k) % s.length()]) //如果相同，则k++;
        k++;
    else
    {
        if (s[(i + k) % s.length()] > s[(j + k) % s.length()])
        {
            i += k + 1; //直接跳到 k + 1位，减小复杂度
            if(i == j)
                j++;
            k = 0;// 将 k 初始化为0
        }    
        else
        {
            j += k + 1;
            if(i == j)
                j++;
            k = 0;
        }
    }
}

ans = min(i, j);//算出 i 和 j 中的较小值。翻转后的字符串算法同上。