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

难度 medium
把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。

注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。

示例 1:

输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。

示例 2:

输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.

示例 3:

输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.

解题思路：

我们通过观察题目中的例子可以发现，由于封装字符串是26个字符按顺序无限循环组成的，那么满足题意的p的子字符串要么是单一的字符，要么是按字母顺序的子字符串。这道题遍历p的所有子字符串会TLE，因为如果p很大的话，子字符串很多，会有大量的满足题意的重复子字符串，必须要用到trick，而所谓技巧就是一般来说你想不到的方法。我们看abcd这个字符串，以d结尾的子字符串有abcd, bcd, cd, d，那么我们可以发现bcd或者cd这些以d结尾的字符串的子字符串都包含在abcd中，那么我们知道以某个字符结束的最大字符串包含其他以该字符结束的字符串的所有子字符串，说起来很拗口，但是理解了我上面举的例子就行。那么题目就可以转换为分别求出以每个字符(a-z)为结束字符的最长连续字符串就行了，我们用一个数组cnt记录下来，最后在求出数组cnt的所有数字之和就是我们要的结果啦。
代码 t32 s52 java

class Solution {
    public int findSubstringInWraproundString(String p) {
        int[] cnt = new int[26];
        int len = 0, res = 0;
        for(int i=0; i<p.length(); i++){
            char t = p.charAt(i);
            if(i> 0 && (t- p.charAt(i-1) == 1 || p.charAt(i-1) - t == 25)) len++;
            else len = 1;
            cnt[t-‘a‘] = Math.max(cnt[t-‘a‘], len);
        }
        for(int c : cnt) res += c;
        return res;
    }
}

代码 t98 s30 cpp

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector<int> cnt(26, 0);
        int len = 0;
        for (int i = 0; i < p.size(); ++i) {
            if (i > 0 && (p[i] == p[i - 1] + 1 || p[i - 1] - p[i] == 25)) {
                ++len;
            } else {
                len = 1;
            }
            cnt[p[i] - ‘a‘] = max(cnt[p[i] - ‘a‘], len);
        }
        return accumulate(cnt.begin(), cnt.end(), 0);
    }
};

参考资料：
https://www.cnblogs.com/grandyang/p/6143071.html

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

原文：https://www.cnblogs.com/zhengxch/p/14888386.html