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

记住这套「是后继就 cur+1、否则归一，dp[当前字符]取较大值」，下面每一帧都在套它。最后把 dp 全部加起来就是答案。

先把 s 平铺出来。我们从左往右扫，维护两样东西:绿色高亮的「当前连续环绕段」，以及右侧 dp 面板「以每个字母结尾的最长段」。开扫。

开局看第 0 个字符 z。它前面没有字符，自己就是一段长度 1 的环绕段，cur = 1。

把它登记进 dp 面板:以字符 z 结尾的最长段目前是 1。dp[z] = 1。

扫到第 1 个字符 a，看它能不能接在前一个 z 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 1。

这里最妙:z 明明是字母表最后一个，但在环上它的下一个绕回 a。算式 (97 − 122 + 26) % 26 = 1，说明 a 正好是 z 的环绕后继，段能接着长。

a 接得上，绿色段延伸到长度 2。再看 dp[a]:之前是 0，现在 cur = 2，取较大值，dp[a] = 2。刷新了。

扫到第 2 个字符 b，看它能不能接在前一个 a 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 2。

b 接得上，绿色段延伸到长度 3。再看 dp[b]:之前是 0，现在 cur = 3，取较大值，dp[b] = 3。刷新了。

扫到第 3 个字符 a，看它能不能接在前一个 b 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 3。

注意 a 不是 b 的下一个（b 的下一个是 c）。算式结果不是 1，环绕段在这里断了。绿色段不能再往左连，cur 要归一，从第 3 个字符重新开始数。

a 接不上，绿色段缩回从第 3 个重新开始，cur = 1。dp[a] 之前是 2，和现在的 1 取较大值，结果 dp[a] = 2。原来的 2 更大,保留不动，这一步没白扫。

扫到第 4 个字符 b，看它能不能接在前一个 a 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 1。

b 接得上，绿色段延伸到长度 2。再看 dp[b]:之前是 3，现在 cur = 2，取较大值，dp[b] = 3。原值更大,保留不动。

扫到第 5 个字符 c，看它能不能接在前一个 b 后面。绿色那段是到上一个字符为止还在生长的环绕段，长度 2。

c 接得上，绿色段延伸到长度 3。再看 dp[c]:之前是 0，现在 cur = 3，取较大值，dp[c] = 3。刷新了。

整条字符串扫完了。dp 面板里每个字母对应「以它结尾的最长环绕段」，这些段互不相同（结尾字母不同就一定不同子串），所以直接把这些长度加起来，就是不同合法子串的总数。

加上 dp[z] = 1（以 z 结尾最长 1 个段，对应 1 个不同子串），当前累计 1。

加上 dp[a] = 2（以 a 结尾最长 2 个段，对应 2 个不同子串），当前累计 3。

加上 dp[b] = 3（以 b 结尾最长 3 个段，对应 3 个不同子串），当前累计 6。

加上 dp[c] = 3（以 c 结尾最长 3 个段，对应 3 个不同子串），当前累计 9。

把 dp[z]=1、dp[a]=2、dp[b]=3、dp[c]=3 全部相加，得到 9。这就是 s = "zababc" 中在环绕串里连续出现的不同子串个数,答案 9。

边界先想清:单字符为 1、重复同字符仍为 1、整段连续时 dp 是 1+2+3。

面试重点:dp 表是为了去重,以及认出「一遍扫描维护状态」母题。