环绕字符串中唯一的子字符串 图解题解

环绕串上的合法子串，重复的怎么只算一次

base 是 26 个小写字母首尾相接的无限环绕串，abc 排下去、z 后面绕回 a。给字符串 s，问它有多少个互不相同的非空子串，正好是环上连续的一段。s = "zab" 时 z、a、b、za、ab、zab 都在环上连着，答案 6；s = "cac" 只有 a、c 合法，答案 2。数的是不同子串个数，重复只算一次。

为什么枚举所有子串再判重会爆

最直接是把 s 的所有子串列出来，逐个判断在不在环上连续，去重后留下不同的。可长度 n 的串有大约 n²/2 个子串，n 一大就爆。而且同一个合法子串会从不同起点被重复数到——s = "abab" 里两段 ab 就是同一个串，会被数两遍。改成按结尾字符给子串归堆，每个不同子串只在它的结尾那格被数一次，判重就免了。

dp[c] 为什么记「以 c 结尾的最长环绕段」

每个合法子串都落在一个结尾字符上。定义 dp[c] 为「s 中以字符 c 结尾、最长的环绕连续段有多长」，26 个字母各占一格。为什么盯最长？环绕串固定，给定结尾 c 和长度 L，往前倒推的字符全被定死，以 c 结尾、长度 L 的合法子串只有一种。于是以 c 结尾的全部不同子串，恰好是长度 1 到 dp[c] 这 dp[c] 个。

一遍扫描更新 dp，加起来为什么不重不漏

从左往右扫 s，维护 cur 表示「到当前字符为止还在生长的环绕段」有多长。当前字符 c 是不是前一个的环绕后继（在字母环上紧跟前一个的那个字母）：是就 cur 加一，不是就 cur 归一从头起段。判后继用 (c − 前一个 + 26) % 26 == 1，加 26 是为了让 z 到 a 也算数（z 是 122、a 是 97，直接相减为负判不出）。每扫到 c 就用 dp[c] 和 cur 取较大值，同一结尾只留最长那次。

扫完把 dp[c] 全加起来就是答案。为什么不会重：以 c 结尾的不同子串恰好是长度 1 到 dp[c] 这 dp[c] 个，一格全数完；结尾不同的两个子串又必然不是同一个。每个不同子串都被它的结尾那格数到、且只数一次，相加不重不漏。

拿示例 s = "zab" 逐格算一遍

z 打头，前面没字符，cur = 1，dp[z] = 1。a 接 z：(97 − 122 + 26) % 26 = 1 是环绕后继，cur = 2，dp[a] = 2。b 接 a：(98 − 97) % 26 = 1 也是后继，cur = 3，dp[b] = 3。扫完 dp[z]=1、dp[a]=2、dp[b]=3，相加 1+2+3 = 6，正是这个例子的答案。

为什么一遍扫描就够，环绕取模最容易漏

一趟扫描每字符做常数次判断，时间 O(n)；dp 表固定 26 格加 cur 一个变量，空间 O(1)。

三处最容易写错。一是环绕判定漏了 z 接 a：不加 26 直接取模，z 到 a 算成负数，本该连上的段被判成断开。二是 dp[c] 直接赋值而非取较大值：同一结尾出现多次，较短的一次会覆盖更长的。三是回头枚举子串判重，退回 O(n²)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findSubstringInWraproundString(self, s: str) -> int:
        f = defaultdict(int)
        k = 0
        for i, c in enumerate(s):
            if i and (ord(c) - ord(s[i - 1])) % 26 == 1:
                k += 1
            else:
                k = 1
            f[c] = max(f[c], k)
        return sum(f.values())

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int f[26]{};
        int n = s.length();
        for (int i = 0, k = 0; i < n; ++i) {
            if (i && (s[i] - s[i - 1] + 26) % 26 == 1) {
                ++k;
            } else {
                k = 1;
            }
            f[s[i] - 'a'] = max(f[s[i] - 'a'], k);
        }
        return accumulate(begin(f), end(f), 0);
    }
};

Java

import java.util.*;
class Solution {
    public int findSubstringInWraproundString(String s) {
        int[] f = new int[26];
        int n = s.length();
        for (int i = 0, k = 0; i < n; ++i) {
            if (i > 0 && (s.charAt(i) - s.charAt(i - 1) + 26) % 26 == 1) {
                ++k;
            } else {
                k = 1;
            }
            f[s.charAt(i) - 'a'] = Math.max(f[s.charAt(i) - 'a'], k);
        }
        return Arrays.stream(f).sum();
    }
}