最小(大)表示法模板

算法用途

有一个首位相连的字符串,我们要寻找一个位置,从这个位置向后形成一个新字符串,我们需要使这个字符串字典序最小(大)。
还可用作字典序最小化,即一个字符串若可以rotating,可以用最小表示法将他们字典序最小化,然后去重。

算法解释

我们这里要i = 0,j = 1,k = 0,表示从i开始k长度和从j开始k长度的字符串相同(i,j表示当前判断的位置)

当我们str[i] == str[j]时,根据上面k的定义,我们的需要进行k+1操作

当str[i] > str[j]时,我们发现i位置比j位置上字典序要大,那么不能使用i作为开头了,我们要将i向后移动,移动多少呢?有因为i开头和j开头的有k个相同的字符,那么就执行 i = i + k +1

相反str[i] < str[j]时,执行:j = j + k +1

最终i和j中较小的值就是我们最终开始的位置

相反如果是最大表示法的话,我们就要求解字典序最大的字符串,那么我们只需要在执行第二或第三个操作时选择较大的那个位置较好了

模板代码

int Get_min()
{
    int n = strlen(s);
    int i = 0,j = 1,k = 0,t;
    //表示从i开始k长度和从j开始k长度的字符串相同
    while(i < n && j < n && k < n)
    {
        t = s[(i+k)%n] - s[(j+k)%n];
        //t用来计算相对应位置上那个字典序较大
        if(!t) k++;//字符相等的情况
        else
        {
            if(t > 0) i += k+1;//i位置大,最大表示法: j += k+1
            else j += k+1;//j位置大,最大表示法: i += k+1
            if(i == j) j++;
            k = 0;
        }
    }
    return min(i,j);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注