## 题目描述：

LeetCode 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.
```

## Python代码：

``````class Solution(object):
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
pattern = 'zabcdefghijklmnopqrstuvwxyz'
cmap = collections.defaultdict(int)
start = end = 0
for c in range(len(p)):
if c and p[c-1:c+1] not in pattern:
for x in range(start, end):
cmap[p[x]] = max(end - x, cmap[p[x]])
start = c
end = c + 1
for x in range(start, end):
cmap[p[x]] = max(end - x, cmap[p[x]])
return sum(cmap.values())
``````

## Python代码：

``````class Solution(object):
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
pattern = 'zabcdefghijklmnopqrstuvwxyz'
cmap = collections.defaultdict(int)
clen = 0
for c in range(len(p)):
if c and p[c-1:c+1] not in pattern:
clen = 1
else:
clen += 1
cmap[p[c]] = max(clen, cmap[p[c]])
return sum(cmap.values())
``````

Pingbacks已关闭。

1. 赤壁的火神 发布于 2016年12月5日 14:58 #

p[c-1:c+1] not in pattern这行代码是不是会增加时间复杂度 我自己不太懂Python是怎么完成这一行体现的功能的 KMP?

2. 在线疯狂 发布于 2016年12月5日 20:24 #

偷懒所以这样写，效率不如直接的前后字符比较。Python中的字符串查找使用了Boyer-Moore 和 Horspool，参考 https://hg.python.org/cpython/file/tip/Objects/stringlib/fastsearch.h