467. 环绕字符串中唯一的子字符串

发表于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

  • 无穷循环DP的处理

思路

1. 问题抽象

给定字符串 \(p\)（由 'a'–'z' 组成），定义无限循环字符串 \[ W=\text{"abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz}\cdots \] 目标：统计 \(p\) 的所有不同非空子串中，有多少个同时也是 \(W\) 的子串。

2. 合法性约束：环上连续

子串 \(t\) 是 \(W\) 的子串，当且仅当 \(t\) 内相邻字符满足“字母环连续”：

  • 普通连续：c -> d（ASCII 差 1）
  • 环回连续：z -> a

形式化地，对任意相邻位置 \(i-1,i\)，要求： \[ p[i]-p[i-1]=1 \quad \text{或} \quad (p[i-1]='z' \land p[i]='a') \] 因此问题变为：在 \(p\) 中，统计所有满足上述相邻约束的子串的不同个数。

3. 去重建模：用“结尾字符 + 长度”刻画唯一子串

3.1 关键事实

在无限循环串 \(W\) 中：

  • 一个合法子串一旦确定了结尾字符 \(c\) 与长度 \(L\)，该子串内容就被环上连续性唯一确定。
  • 同一个结尾字符 \(c\)，长度不同（例如 \(L=2\) 与 \(L=3\)）对应的子串必不相同。

因此，“不同子串去重”可以转为对每个结尾字符统计可覆盖的长度范围。

3.2 压缩状态的核心结论

若存在以字符 \(c\) 结尾的最长合法子串长度为 \(M\)，那么以 \(c\) 结尾的合法子串长度集合恰好覆盖： \[ 1,2,\dots,M \] 对应 \(M\) 个互不相同的子串。

于是只要知道每个字符 \(c\) 的最大值 \(M\)，就能直接累加得到答案。

4. 状态设计与转移方程

4.1 局部 DP（按位置）

定义： \[ f[i] = \text{以 } p[i] \text{ 结尾的最长合法连续子串长度} \] 转移： \[ f[i]= \begin{cases} f[i-1]+1, & \text{若 } p[i]\text{ 与 }p[i-1]\text{ 在环上连续}\\ 1, & \text{否则} \end{cases} \] 其中“环上连续”判定为： \[ (p[i]-p[i-1]=1)\ \ \text{或}\ \ (p[i-1]='z' \land p[i]='a') \]

4.2 去重压缩（按结尾字符）

定义： \[ \text{end}[c] = \max \{ f[i] \mid p[i]=c \} \] 含义：以字符 \(c\) 结尾的合法子串中，能出现的最大长度。

5. 答案构造与正确性要点

最终不同子串总数为： \[ \sum_{c='a'}^{'z'} \text{end}[c] \] 正确性理由（要点式）：

  1. 任意合法子串都对应某个结尾字符 \(c\) 和长度 \(L\)。
  2. 对固定 \(c\)，若 \(\text{end}[c]=M\)，则长度 \(1\) 到 \(M\) 的合法子串都必然出现（作为某个位置的连续后缀）。
  3. 对固定 \(c\)，不同长度对应不同子串；对不同 \(c\) 结尾字符不同，子串也不同。
  4. 因此对 26 个字符分别计数并求和，得到的就是不同合法子串总数。

6. 复杂度

  • 时间复杂度：\(O(n)\)
  • 空间复杂度：使用数组 end[26] 为 \(O(1)\)；若额外存 f[i] 则为 \(O(n)\)。本题实际可只用一个变量滚动维护当前长度。

7. 无穷次循环 DP 的通用范式（可迁移）

这类题的常用处理框架：

  1. 不在“无限对象”上做 DP，而是在输入串上扫描。
  2. 找到一个有限状态集合，能把“无限结构中的唯一对象”映射为有限表示（本题是 26 个结尾字符）。
  3. 去重计数常可转为“每个状态的最大覆盖范围”（本题是最大长度）。
  4. 在线更新覆盖范围，最后汇总有限状态。

8. AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    static const int maxn = 1e5 + 5;

    int findSubstringInWraproundString(string s) {
        // f[i]: 以 s[i] 结尾的最长合法连续子串长度
        // （本题可只用一个 cur 变量滚动维护；这里保留 f 也是正确的）
        int f[maxn] = {};

        // end[k]: 以字符 ('a' + k) 结尾的合法子串所能达到的最大长度
        // 用它来完成“去重计数”的压缩
        int end[26] = {};

        // 初始化第一个位置：单字符总是合法连续子串，长度为 1
        f[0] = 1;
        end[s[0] - 'a'] = 1;

        for (int i = 1; i < (int)s.size(); ++i) {
            // 默认不与前一字符形成环上连续，最长长度从 1 开始
            f[i] = 1;

            // 若 s[i-1] -> s[i] 在字母环上连续，则可以接到前一段后面
            // 1) 普通连续：s[i] == s[i-1] + 1
            // 2) 环回连续：s[i-1] == 'z' 且 s[i] == 'a'
            if (s[i] == s[i - 1] + 1 || (s[i] == 'a' && s[i - 1] == 'z')) {
                f[i] = max(f[i], f[i - 1] + 1);
            }

            // 更新以当前结尾字符为终点的最大长度覆盖
            int idx = s[i] - 'a';
            end[idx] = max(end[idx], f[i]);
        }

        // end[0..25] 的和就是不同合法子串总数
        int sum = 0;
        for (int i = 0; i < 26; ++i) {
            sum += end[i];
        }
        return sum;
    }
};