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

把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 现在给定另一个字符串 pLeetCode 467. 环绕字符串中唯一的子字符串 - 图1#card=math&code=%281%20%3C%3D%20p.length%20%3C%3D%2010%5E5%29) 。返回 s 中 唯一 的 p 的 非空子串 的数量 。 p 由小写英文字母构成。相关标签：字符串, 动态规划。

Unique Substrings in Wraparound String

We define the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this:"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". Given a string p, return the number of unique non-empty substrings of pLeetCode 467. 环绕字符串中唯一的子字符串 - 图2#card=math&code=%281%20%3C%3D%20p.length%20%3C%3D%2010%5E5%29) are present in s. p consists of lowercase English letters. Related Topics: String, Dynamic Programming.

  1. Input: p = "a"
  2. Output: 1
  3. Explanation: Only the substring "a" of p is in s.
  1. Input: p = "cac"
  2. Output: 2
  3. Explanation: There are two substrings ("a", "c") of p in s.
  1. Input: p = "zab"
  2. Output: 6
  3. Explanation: There are six substrings ("z", "a", "b", "za", "ab", and "zab") of p in s.

题意非常的绕。给我们一个字符串p然后让我们找出p里面有多少个不同的子串，这里的不同指的是字符串是不是相等，跟位置没有关系。这题就是问我们p里面有多少不同的子串是在s里面出现过的。注意我们的s是二十六字母的无限循环字符串，而我们的p只是个字符串！所以这题的本质就是给我们一个p然后问我们的p里面有多少不同的子串使得这个子串是一段连续字符 (也就是无限环绕字符串)。

我们先考虑一个简单的问题，假设不判重的情况下我们不是求不同的连续子串的个数，而是求所有子串里面有多少子串是连续子串。那这个该怎么求呢？我们发现我们可以把p分成若干段，使得每一段都是连续子串。我们去找到所有不连续的两个字符然后把它们断开，因为不连续的两个字符必然不是在某一个连续子串中间。这样的话这个字符串就会被切割成若干部分，每一部分内部都是一个连续子串。而且不同部分之间是不可能有横跨这种子串出现的，因为不同部分之间的两个相连字符是不连续的。

我们划分完后就会出现若干个连续子串，那么每一个连续子串里面有多少个不同子串呢？有很多不同的子串。假设某一部分长度为k，那么长度为1的子串有k个，长度为2的子串有k-1个，长度为3的子串有k-2个…所以这里面不同子串的个数应该是k(k+1)/2个。这是不判重的情况，那么判重的情况该怎么做呢？

判重的话主要是我们去考虑怎么确定一个子串，可以发现连续子串一旦起点确定了，那么后面就完全确定了，所以我们想确定一个唯一子串的话只需要确定两点就可以了：（1）起始字符；（2）长度。长度怎么确定呢？所以说我们在考虑所有不同子串的时候我们只需要确定一下以每个起始字符开头的连续字符的最大长度就可以了。比如说以a开头的连续子串最大长度是26，那么以a开头的连续子串的个数就是26。所以说以某个字符开头的连续子串的个数就等于以这个字符开头的最大连续子串的长度。所以我们求完以每个字符开头的连续子串的最大长度之后，我们只需要把每个字符的连续子串的最大长度相加就是我们的答案！

所以我们接下来只需要求一下以每个字符开头的连续子串的最大长度就可以了。由于连续子串不能横跨段与段之间，所以我们可以先把每一段找出来。对于某一段，以每个字符开头的连续子串的最大长度必然是走到该段的结尾(也就是这一段与下一段的分割处)。所以对于每段的内部我们只需要枚举一下起点就可以了，终点必然都是在该段的最后一个点。

所以我们的思路是这样，开一个哈希表去存储一下以每一个字符开头的连续子串的最大长度，然后用双指针算法去找出来每一个区间，然后在每一个连续区间内部去枚举一下起点，更新一下每个起点字符开头的连续子串的最大长度。

整个算法时间复杂度为O(n),空间复杂度O(∣Σ∣)，其中 ∣Σ∣ 为字符集合的大小，本题中字符均为小写字母，故 ∣Σ∣=26。然后看一下代码怎么写：

  1. class Solution {
  2. public:
  3.     int findSubstringInWraproundString(string p) {
  4.         unordered_map<char,int> cnt;
  5.         for(int i=0;i<p.size();) {
  6.             int j=i+1;
  7.             // 当前字符是和下一个字符相连的话，区间往后加长
  8.             while(j<p.size() && (p[j]-p[j-1]==1 || p[j]=='a' && p[j-1]=='z')) j++;
  9.             // 更新长度
  10.             while(i<j) 
  11.         }
  12.         int res=0;
  13.         for(auto [a,b]:cnt) res+=b;
  14.         return res;
  15.     }
  16. };
  1. go语言是真难用，草