# 467. Unique Substrings in Wraparound String 环绕字符串中唯一的子字符串

## # 题目描述：

Consider the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this: `"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."`.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

``````Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.
``````

Example 2:

``````Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.
``````

Example 3:

``````Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.
``````

## # 解题方法

``````class Solution:
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
count = collections.defaultdict(int)
N = len(p)
_len = 0
for i in range(N):
if i > 0 and (ord(p[i]) - ord(p[i - 1]) == 1 or (p[i] == 'a' and p[i - 1] == 'z')):
_len += 1
else:
_len = 1
count[p[i]] = max(count[p[i]], _len)
return sum(count.values())
``````

http://www.cnblogs.com/grandyang/p/6143071.html

## # 日期

2018 年 10 月 16 日 —— 下雨天还是挺舒服的