计算含指定单词恰好一次的定长字符串数量及大N值优化方案

针对你提出的大N场景下的计数需求，最优方案是KMP前缀函数+动态规划+矩阵快速幂，时间复杂度仅和单词W的长度L以及logN相关，完全可以处理N到1e18量级的计算需求，无需枚举所有可能的单词位置。

核心思路 #

前置处理：计算单词W的前缀函数 #

首先计算长度为L的单词W的KMP前缀函数数组，这个数组可以直接给出W所有的「border」（既是前缀又是后缀的子串），天然解决你手动计算时需要处理的单词重叠问题，不需要单独枚举排除重叠场景。比如你示例中的radar，前缀函数计算结果为[0,0,0,0,1]，直接就能知道它的最长公共前后缀长度为1，对应重叠3个字符的重复出现场景。

动态规划状态定义 #

我们定义两组状态：

• dp[i][s]：长度为i的字符串，从未出现过W，且当前字符串后缀和W的前缀匹配了s个字符的总数量
• f[i]：长度为i的字符串，恰好出现过一次W的总数量

状态转移规则 #

1. dp状态转移
   枚举下一个添加的字符c（共26种可能），根据KMP的匹配规则计算加入c后的新匹配长度s'：
   • 若s' < L，说明还没出现W，合法转移到dp[i+1][s']，贡献为dp[i][s]
   • 若s' == L，说明新增了一次W的出现，不进入dp数组，计入f的转移增量
2. f状态转移
   有两种合法的转移路径：
   • 长度为i的字符串已经恰好有一次W，后续加任意26种字符都合法，贡献为f[i] * 26
   • 长度为i的字符串从未出现过W，加字符后刚好第一次出现W，贡献为所有触发s'=L的dp[i][s]之和

最终我们要求的结果就是f[N]。

大N场景的加速优化 #

因为上述所有转移都是线性变换，我们可以把整个转移过程转换成矩阵乘法的形式，再通过矩阵快速幂计算N步后的结果，时间复杂度可以降到O((2L)^3 * logN)，其中L是单词W的长度，哪怕L到1e3、N到1e18也可以快速算出结果。

示例验证 #

你给出的N=10、W=radar的场景，用上述方法计算得到的结果和你手动枚举的结果一致，均为71288150，证明方案正确性。

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