Booth's Algorithm求字典序最小字符串旋转的代码解释咨询

带注释的完整代码 #

def least_rotation(S: str) -> int:
    """Booth's algorithm，求字符串的最小字典序旋转的起始下标"""
    n = len(S)
    S += S  # 拼接两倍字符串，所有旋转结果都是该串长度为n的子串，避免模运算
    f = [-1] * len(S)  # 失败函数数组，类似KMP的部分匹配表，存储最长公共前后缀长度
    k = 0  # 目前找到的最小旋转的起始下标候选，是算法核心维护的最优值
    for j in range(1, len(S)):
        sj = S[j]  # 当前遍历到的右指针位置的字符
        # j-k是当前j相对于当前最优起始点k的偏移量，取前一个偏移的失败函数值
        i = f[j - k - 1]
        # 处理不匹配的情况，回退公共前缀
        while i != -1 and sj != S[k + i + 1]:
            # 当前字符比k对应位置的字符小，说明k已经不可能是最优解，更新k的位置
            if sj < S[k + i + 1]:
                k = j - i - 1
            i = f[i]
        # 出循环后要么i=-1，要么sj和对应位置匹配
        if sj != S[k + i + 1]:
            # 此时i一定是-1，没有公共前缀可以复用，直接比较当前字符和k位置的首字符
            if sj < S[k]:
                k = j
            f[j - k] = -1
        else:
            # 匹配成功，更新失败函数值为当前公共前后缀长度+1
            f[j - k] = i + 1
    # 最终k一定小于原串长度n，就是最小旋转的起始下标
    return k

核心变量与下标逻辑说明 #

关键变量含义 #

• k：全程维护的当前最优最小旋转起始下标，遍历过程中所有小于k的起始点都已经被证明不可能是最优解，最终返回的就是这个值
• f数组：复用了KMP算法的部分匹配思想，存储以k为起点的子串的最长公共前后缀长度，避免重复比较已经匹配的字符
• j：遍历双倍字符串的右指针，用来和k开头的子串做逐位对比，判断是否有比k更优的起始点

容易困惑的下标解释 #

• j - k：当前j指针相对于当前最优起始点k的偏移量，比如k=2，j=5，偏移量就是3，对应S[k+3] = S[5]
• j - k - 1：取前一个偏移位置的失败函数值，用来获取之前已经匹配到的最长公共前后缀长度，跳过不需要重复比较的部分
• k + i + 1：当前需要和S[j]对比的、k开头子串的对应位置，i是已经匹配的公共前后缀长度，加1就是下一个要比较的位置

算法核心逻辑 #

算法整体时间复杂度为O(n)，因为j指针只会单向移动，失败函数的回退操作总次数也是线性的：

1. 拼接双倍字符串后，所有可能的旋转结果都可以表示为该串中长度为n的连续子串，不需要再做模运算
2. 全程维护当前最优起始点k，一旦发现更优的起始点就直接更新k，跳过所有不可能更优的起始位置
3. 用失败函数复用之前的匹配结果，避免逐位回溯比较，和KMP算法的优化思路一致

内容的提问来源于stack exchange，提问作者juraj14466