題意
我們有一個串s，是由abcdefg…z循環(huán)連接而成的， 給出一個字符串p，求p得所有子串在s中出現(xiàn)的次數(shù)。
思路
最初的想法是用d[i,j]來表示：p中的第i位，是一個j連續(xù)的串的出現(xiàn)次數(shù)和，但是這樣會算重，比如我們的”cac”，里面c會被重復統(tǒng)計兩次。
那么，我們就需要考慮如何避免算重。
假如我們的p中同時包含“abcd”和”bcd”，考慮”abcd”的子串：a, b, c, d, ab, bc, cd, abc, bcd, abcd。再考慮”bcd”的子串：b, c, d, bc, cd, bcd。明顯能夠發(fā)現(xiàn)”bcd”的子串是屬于”abcd”的子串的。即對于我們的每一個字母x，考慮以x結(jié)尾的連續(xù)字符串，只需要取最長的那一個來計算結(jié)果即可。
所以，我們用d[i]表示：以i結(jié)尾的滿足條件的字符串的統(tǒng)計次數(shù)。最后的結(jié)果為a - z的累計值。
代碼
class Solution {public: bool judge(char x, char y) { return (y == x + 1 || x - y == 25); } int findSubstringInWraPRoundString(string p) { int n = p.length(); if (n == 0) return 0; vector<int> d(30, 0); d[p[0] - 'a'] = 1; int len = 1; for (int i = 1; i < n; i++) { if (judge(p[i - 1], p[i])) len++; else len = 1; d[p[i] - 'a'] = max(d[p[i] - 'a'], len); } int res = 0; for (int i = 0; i < 26; i++) res += d[i]; return res; }};
