字符串python模板

​ 如果字符串 的同长度的前后缀完全相同，即 则称此前缀(后缀)为一个 ，根据语境，有时 也指长度。特殊的，字符串本身也可是其本身的 具体看语境。

周期和循环节

​ 对于字符串 和正整数 ，如果 ，对于 成立，则称 为 的一个周期。特别的， 一定是 的一个周期。

​ 若字符串 的周期 满足 ，则称 为 的一个循环节。特别的， 一定是 的一个循环节。

性质

• 。因此，字符串的周期性质等价于 性质，求周期也等价于求 。( 不具有二分性)
• ，求 的所有 等价于求所有前缀的最大

算法

数组和 数组的预处理

1. 初始化
2. 不断尝试扩展匹配长度 ，如果扩展失败（下一个字符不相等），令 变为 ，直至 为 （应该重新开始从头开始匹配）。
3. 如果能够扩展成功，匹配长度 就增加 ， 的值就是 。

根据势能分析法可证明，复杂度为 常量在 左右

class Kmp:
    def __init__(self, t):
        """字符串从 1 开始
        t:模式串
        s:原字符串
        """
        n = len(t)
        nxt = [0] * n

        for i in range(2, n):  # 预处理next数组
            nxt[i] = nxt[i - 1]
            while nxt[i] and t[i] != t[nxt[i] + 1]:
                nxt[i] = nxt[nxt[i]]
            nxt[i] += 1 if t[i] == t[nxt[i] + 1] else 0

        self.nxt = nxt

    def get_f(self, t, s):
        nxt = self.nxt,len(s)
        n,m = len(nxt),len(s)
        f = [0]*m
        j = nxt[1]
        for i in range(1, m + 1):  # 预处理f数组
            while j and (j == n or t[i] != s[j + 1]): j = nxt[j]
            if t[i] == s[j + 1]: j += 1
            f[i] = j
            # if f[i] == n: (t 在 s 中某一次出现)
        return f