題目

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.

分析

已知有一個無限循環(huán)的字符串s: "abc...xyz"+"abc..xyz"...+...，給你一個字符串奶卓，問這個字符串有多少個子串在s中擂送。
這道題開始想用兩個指針做非迹，但是會引起重復顿仇，比如cac中會得到c 和 ac 和c温数。
其實應該使用動態(tài)規(guī)劃宙彪，代碼很好寫，思路不好想等限。
得到以每個字符結尾的最大合乎要求的長度爸吮，加起來就是最終結果
比如abcd以d結尾，長度為4望门，則有abcd,bcd,cd,d這四個子串形娇，再加上以a、b筹误、c結尾的桐早，就是最終結果，而且取最長的可以避免重復厨剪。

The idea is, if we know the max number of unique substrings in p ends with 'a', 'b', ..., 'z', then the summary of them is the answer. Why is that?

1. The max number of unique substring ends with a letter equals to the length of max contiguous substring ends with that letter. Example "abcd", the max number of unique substring ends with 'd' is 4, apparently they are "abcd", "bcd", "cd" and "d".
2. If there are overlapping, we only need to consider the longest one because it covers all the possible substrings. Example: "abcdbcd", the max number of unique substring ends with 'd' is 4 and all substrings formed by the 2nd "bcd" part are covered in the 4 substrings already.
3. No matter how long is a contiguous substring in p, it is in s since s has infinite length.
4. Now we know the max number of unique substrings in p ends with 'a', 'b', ..., 'z' and those substrings are all in s. Summary is the answer, according to the question.

代碼

public int findSubstringInWraproundString(String p) {
    // count[i] is the maximum unique substring end with ith letter.
    // 0 - 'a', 1 - 'b', ..., 25 - 'z'.
    int[] count = new int[26];
    
    // store longest contiguous substring ends at current position.
    int maxLengthCur = 0; 

    for (int i = 0; i < p.length(); i++) {
        if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || (p.charAt(i - 1) - p.charAt(i) == 25))) {
            maxLengthCur++;
        }
        else {
            maxLengthCur = 1;
        }
        
        int index = p.charAt(i) - 'a';
        count[index] = Math.max(count[index], maxLengthCur);
    }
    
    // Sum to get result
    int sum = 0;
    for (int i = 0; i < 26; i++) {
        sum += count[i];
    }
    return sum;
}