KMP 延伸：num 数组求解与乘积计算 题解

问题分析

本题要求基于 KMP 算法的 next 数组，计算 num 数组，并输出所有 (num_i + 1) 的乘积对 1,000,000,007 取模的结果。核心在于理解 num 数组的定义（满足“前缀后缀重合且不重叠”的子串数量），并通过 next 数组的回溯特性高效求解。

关键概念

• next 数组：对于字符串前 i 个字符的子串，next[i] 是其最长的“既是前缀又是后缀（非自身）”的子串长度。
• num 数组：num[i] 是前 i 个字符的子串中，满足“既是前缀又是后缀且不重叠”的子串数量（不重叠即子串长度 len ≤ i/2）。

算法步骤

1. 计算 next 数组：采用 KMP 算法的标准流程，时间复杂度 O(L)。

   • 初始化 next[0] = next[1] = 0，j = 0（表示当前匹配的前缀长度）。
   • 遍历字符串 i 从 1 到 L-1：
     • 若 s[i] == s[j]，则 j++，next[i+1] = j；
     • 否则，j 回溯到 next[j]，重复判断直至 j=0 或匹配成功。

2. 计算 num 数组：通过回溯 next 链，统计所有满足 len ≤ i/2 的前缀后缀长度，利用缓存避免重复计算，时间复杂度 O(L)。

   • 对每个 i，从 current = next[i] 开始回溯：
     • 若 current > 0 且 current ≤ i/2，则 num[i] = 1 + num[current]；
     • 若 current > i/2，则继续回溯 current = next[current]；
     • 若 current = 0，则 num[i] = 0。

3. 计算乘积：遍历 num 数组，累加 (num_i + 1) 的乘积并对 1,000,000,007 取模。

复杂度分析

• 时间复杂度：O(L)（next 数组和 num 数组的计算均为线性时间）。
• 空间复杂度：O(L)（存储 next 数组和 num 数组）。

该算法可高效处理 L ≤ 10^6 的数据规模，完全符合题目要求。