467. 環繞字符串中唯一的子字符串

定義字符串?base?為一個?"abcdefghijklmnopqrstuvwxyz"?無限環繞的字符串，所以?base?看起來是這樣的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

給你一個字符串?s?，請你統計并返回?s?中有多少?不同非空子串?也在?base?中出現。

思路：本題中要求求所有存在的非空字串，且字串不能重復。首先先求所有存在的字串數目。

dp[i]表示以i結尾的所有字串的數目，則dp[i]=dp[i-1](若第i個元素可以和前面的元素組成字串)或者為0（不能組成字串）。此時dp中存放著所有非空字串的數目，但需要去重。去重主要利用了字串之間的特點，即若以同一個字符結尾，則二者必定一個是另一個的子串（因為以同一個字符結尾前面一定一樣），則只需要存放其中更大的那個就行（因為dp[i]存放以i位置字符結尾的所有字串的數目，一定包含更少的那一部分）。

初始化時dp中每個元素是1，因為只有本身一個字符一定能構成子串。

dp[i]+=dp[i-1]，用+=，可以想成dp[i-1]的所有可能加上了最后一個字符的數目(dp[i-1])，和只有最后一個字符的數目（dp[i]）之和構成新的dp[i];

class Solution {
public:int findSubstringInWraproundString(string s) {set<string>sets;int n=s.size();vector<int>ret(n,1);for(int i=1;i<n;i++){if(s[i]-s[i-1]==1||s[i]=='a'&&s[i-1]=='z'){ret[i]+=ret[i-1];}}vector<int>num(26,0);for(int i=0;i<n;i++){int low=s[i]-'a';num[low]=max(num[low],ret[i]);}       int sum=0;for(auto e:num){sum+=e;}return sum;}};