Chapter 4. 串

考点

• KMP 算法

  • 求 next 数组

    1. 计算前后缀公共最大长；
    2. 将计算结果右移一位，最左位补 -1 ；
    3. 所有位 +1。

  • 求 nextval数组

    if ( s[next[j]] == s[j] ) {
        next[j] = next[next[j]]
    }
    

  • next 数组中的值对应字符串 s[1...n] 的下标。

  • 时间复杂度： O(m+n) 。

    主串不回退，模版串近似于不回退。

    通常由于 m\ll n ，所以 O(n) 亦可。