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

---

给定一个a-z的无限循环字符串s，比如…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….。再给定一个字符串p，问p有多少个子串是在s中的。 在s中的子串需要满足一定的条件，比如单个字符可以，还有就是连续的字符串，即abcd…之类的。 注意第二个样例中，p有两个相同的子串c，但是结果中只统计一次，所以比如p中有多个以同一个字符结尾的子串，我们只需要统计最长的那个就好了。比如P=”abcdefgxxxxcdefgyyy”。以g结尾的连续子串有两个，分别是abcdefg和cdefg，但是我们只需要保留前者就好了，因为前者最长，它的所有子串已经包含后者的所有子串了。而子串的长度就是以g为结尾且在s中的子串的长度，比如这里就是7。 所以我们只需要统计以每个字符结尾的最长连续子串的长度，然后把所有长度加起来，就是最终结果。 注意abcdefg以g结尾的长度是7，也就是abcdefg有7个子串是在s中的。abcdefg也包含abcdef，以f结尾的长度是6，也就是abcdef有6个子串在s中。 代码如下： [cpp] class Solution { public: int findSubstringInWraproundString(string p) { vector<int> count(26, 0); int len = 0; for (int i = 0; i < p.size(); ++i) { if (i > 0 && (p[i] – p[i – 1] == 1 || p[i] – p[i – 1] == -25))++len; else len = 1; count[p[i] – ‘a’] = max(count[p[i] – ‘a’], len); } int ans = 0; for (int i = 0; i < 26; ++i)ans += count[i]; return ans; } }; [/cpp] 本代码提交AC，用时9MS。]]>