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.
public int findSubstringInWraproundString(String p) {
int[] count = new int[26];
int maxlengthcur =0;
int N = p.length();
for(int i=0;i<N;i++) {
if(i>0&&(p.charAt(i)-p.charAt(i-1)==1||(p.charAt(i)-p.charAt(i-1)==-25))) {
maxlengthcur++;
}else {
maxlengthcur=1;
}
int t = p.charAt(i)-'a';
count[t]=Math.max(count[t], maxlengthcur);
}
int sum=0;
for(int i=0;i<26;i++) {
sum = sum+count[i];
}
return sum;
}
这其实是一个动态规划的问题；
举例， ABCD BCD CD D。 ABCD会囊括（BCD，CD，D）这些字符串的子字符串。
