题目大意

给定一个长度为 $N$ 的字符串 $s$ 和整数 $K$，机器人内存存储 $K$ 个字符，按循环方式执行。统计所有长度至少为 $K+1$ 的连续子串中，满足循环模式匹配条件的子串数量。

解题思路

核心思想

双指针 + 循环模式匹配性质

1. 循环模式性质：如果一个子串 $s[i..j]$ 匹配长度为 $K$ 的循环模式，那么对于任意位置 $p$，有 $s[p] = s[p-K]$（在有效范围内）

2. 双指针扫描：对于每个起始位置 $i$，找到最远的 $j$ 使得 $s[i..j]$ 满足循环模式条件

3. 贡献计算：对于每个 $i$，满足条件的子串数量为 $j - i - K$

算法流程详解

1. 循环模式条件

对于子串 $s[i..j]$ 要匹配长度为 $K$ 的循环模式，需要满足：

• 对于所有 $p \in [i+K, j]$，有 $s[p] = s[p-K]$

2. 双指针扫描过程

• i：子串起始位置（从左到右扫描）
• j：当前满足循环模式条件的最远位置

对于每个 $i$：

1. 将 $j$ 初始化为 $\max(i+K, j)$，保证长度至少为 $K+1$
2. 向右扩展 $j$，只要 $s[j] == s[j-K]$ 就继续扩展
3. 当条件不满足时停止，此时 $s[i..j-1]$ 是满足条件的最大子串

3. 贡献计算

对于起始位置 $i$，满足条件的子串包括：

• $s[i..i+K]$ 到 $s[i..j-1]$ 的所有子串
• 总数量为：$(j-1) - (i+K) + 1 = j - i - K$

举例说明

对于样例：

K = 2
s = "zabacabab"

扫描过程：

• i=1: j从3开始，扩展失败，贡献 3-1-2=0
• i=2: j从4开始，扩展到5，贡献 5-2-2=1 ("aba")
• i=3: j从5开始，扩展到6，贡献 6-3-2=1 ("aca")
• i=4: j从6开始，扩展到8，贡献 8-4-2=2 ("aba", "abab")
• i=5: j从7开始，扩展到9，贡献 9-5-2=2 ("bab", "baba")
• i=6: j从8开始，扩展失败，贡献 8-6-2=0
• ...（继续扫描）

总贡献 = 0+1+1+2+2+0+... = 5

复杂度分析

• 时间复杂度：$O(N)$

  • 每个字符最多被 $j$ 指针访问一次
  • 每个字符最多被 $i$ 指针访问一次

• 空间复杂度：$O(N)$

总结

本题的巧妙解法在于：

1. 利用循环模式的性质：将复杂的循环匹配条件转化为简单的字符相等比较

2. 双指针的单调性：$j$ 指针只会向右移动，不会回退，保证线性复杂度

3. 简洁的贡献计算：通过 $j - i - K$ 直接计算满足条件的子串数量