一、题目：

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

思路：动态规划：时间O（n），空间O（1）

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

dp【i】表示以26个字母中第i个字母作为结尾的连续子串个数。dp[0] 表示以a为结尾的，dp[1]表示以b为结尾的……。

我们看abcd这个字符串，

以a为结尾的子字符串为a，dp[0] = 1

以b为结尾的子字符串为b，ab 。dp[1] = 2

以c为结尾的子字符串为c，bc，abc。dp[2] = 3

以d结尾的子字符串有abcd, bcd, cd, d，故 i = 3，dp[3] = 4。

结果为：1+2+3+4 = 10

题目可以转换为分别求出以每个字符(a-z为结束字符的最长连续字符串就行了，我们用一个数组res记录下来，最后在求出数组res的所有数字之和就是结果。

代码：

def findSubstringInWraproundString(p):    if not p:        return 0    n = len(p)    m = 0    dp = [0] * 26    for i in range(n):            # if dp[i+1][j] == 1 and dp[i][j-1] == 1:        if i > 0 and (ord(p[i]) - ord(p[i-1]) == 1 or ord(p[i]) - ord(p[i-1]) == -25):             m += 1         else:            m = 1        dp[ord(p[i]) - 97] = max(dp[ord(p[i]) - 97] ,m)    res = sum(dp)    return resp = "zabbyz"findSubstringInWraproundString(p)