如何用C语言高效计算字符串前缀与另一字符串的相似度得分？

问题1：是否存在O(|S| + |C|)复杂度的算法组合？ #

是的，完全可以通过KMP失败数组+后缀自动机/AC自动机的组合，在O(|S| + |C|)时间内完成H（命中次数）和L（抄袭可能性）的计算：

• L值计算：基于KMP失败数组，用动态规划线性处理所有C的前缀，时间复杂度O(|C|)。
• H值计算：有两种高效方案可选：
  • 后缀自动机方案：先将S构建为后缀自动机（O(|S|)时间），再遍历C的每个前缀，在自动机中查询其在S中的出现次数（总时间O(|C|)）。
  • AC自动机方案：将C的所有前缀作为模式串构建AC自动机（本质是对C构建字典树+失败指针，O(|C|)时间），然后遍历S一次统计各前缀的出现次数（O(|S|)时间）。

两种方案均能严格满足O(|S| + |C|)的时间要求，适配长度达5×10^6的字符串。

问题2：如何用动态规划高效计算每个前缀的L值？ #

L值的计算核心是利用KMP的失败数组（fail数组），结合动态规划避免重复计算，步骤如下：

1. 构建C的失败数组 #

对字符串C计算KMP的fail数组，其中fail[i]表示C的前i个字符组成的前缀中，既是前缀又是后缀的最长子串的长度（索引从1开始，对应前缀长度i）。

2. 动态规划递推L值 #

定义dp[i]为C的前i个字符前缀的L值：

• 初始条件：dp[1] = 1（长度为1的前缀只有自身满足条件）。
• 递推公式：对于i>1，dp[i] = dp[fail[i]] + 1（约定dp[0] = 0）。

原理：fail[i]对应的前缀是当前前缀最长的“前后公共前缀”，所有满足条件的子串包含该最长前缀的全部满足条件子串，再加上当前前缀自身，因此只需在dp[fail[i]]的基础上加1即可。

这种递推是线性的，每个dp[i]仅依赖dp[fail[i]]，时间复杂度O(|C|)，完全符合递增计算的要求。

例如，对于C="ababab"，其fail数组为[0,0,1,2,3,4]（索引1-6），对应的dp数组为：

• dp[1] = 1
• dp[2] = dp[0] + 1 = 1
• dp[3] = dp[1] + 1 = 2
• dp[4] = dp[2] + 1 = 2
• dp[5] = dp[3] + 1 = 3
• dp[6] = dp[4] + 1 = 3

这与实际结果一致："ababab"的满足条件前缀有长度6、4、2，共3个，L值为3。

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