题目：环绕字符串中唯一的子字符串

• 把字符串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”。.

来源：力扣（LeetCode）第467题

链接：https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string

分析：

• 动态规划问题
• 遇到这种子字符串问题，我们可以考虑状态为以第i个结尾时有多少种情况。
• 例如abcd,a结尾时只有1种情况，b结尾时只有2种情况，c结尾时有3种情况，d结尾时有4中情况。
• 我们把这些值存在一个长度为26的dp数组中，按顺序放进来。
• 如果例子为abcdbcde，其中bcd都是重复的，不应该重复计算。我们可以进行比较，把相同状态下(都是以i结尾)值较大的那个更新进去。
• 例如b，它在abcd中值是2，ab,b。而在bcd中只有b，所以我们只要选择较大的2，那么后者的情况也会包含在内。
• 再比如c在前者有3个，abc,bc,c。后者有2个，bc,c,前者依然包括后者。
• dp数组算出后，我们将dp数组中赋过值的数相加求和，就是最终答案。

代码：

class Solution {
    public int findSubstringInWraproundString(String p) {
        int len = p.length();
        if (len == 0) return 0;
        int[] dp = new int[26];
        char[] pchar = p.toCharArray();
        int succession = 1;
        dp[pchar[0]-'a'] = succession;
        for (int i = 1; i < len; i++) {
            if (pchar[i] - pchar[i-1] == 1 || pchar[i-1] - pchar[i] == 25) {
                succession++;
            } else {
                succession = 1;
            }
            dp[pchar[i]-'a'] = Math.max(dp[pchar[i]-'a'], succession);
        }
        int ans = 0;
        for (int i : dp) ans += i;
        return ans;
    }
}

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        l = len(p)
        if l == 0: return 0
        dp = [0 for _ in range(26)]
        dp[ord(p[0])-97] = 1
        succession = 1
        for i in range(1, l):
            if ord(p[i]) - ord(p[i-1]) == 1 or ord(p[i-1]) - ord(p[i]) == 25:
                succession += 1
            else:
                succession = 1
            dp[ord(p[i])-97] = max(dp[ord(p[i])-97], succession)
        return sum(dp);

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        int len = p.length();
        if (len == 0) return 0;
        int ans = 0, curLen = 1;
        int* dp = new int[26];
        for (int i = 0; i < 26; i++) dp[i] = 0;
        dp[p[0]-'a'] = 1;
        for (int i = 1; i < len; i++) {
            if (p[i] - p[i-1] == 1 || p[i-1] - p[i] == 25) {
                ++curLen;
            } else {
                curLen = 1;
            }
            dp[p[i]-'a'] = max(dp[p[i]-'a'], curLen);
        }
        for (int i = 0; i < 26; i++) ans += dp[i];
        return ans;
    }
};