467.环绕字符串中唯一的子字符串
467.环绕字符串中唯一的子字符串
题解
题目：给一个a到z的字符串s，并且定义该字符串s是无限环绕的，即a…xyzabcd…yzabc…,给一个字符串p，问p中的有多少个子串，出现在s中。例如p=cab,则 a,b,c,ab这4个子串在s中出现过
思路：动态规划
p=bcd b 1(b) bc 2(c,bc) bcd 3(d,cd,bcd) p=cab c 1(c) ca 1(a) cab 2(b,ab) 在周期字符串s中，如果知道了子串的最后一个字符，以及子串长度，那么该字符串就被确定了 题目要求的是不同子串个数，那么对于相同字符结尾的子串，长的子串必定包含短的子串---bcd abcd 定义dp[i]:在p中以字符串i结尾的子串的 最长长度,知道了最长长度，那么就知道了以i结尾的不同子串的个数了 递推公式：如果p[i]是p[i-1]的下一个字母，则递增k，否则k=1，重新开始计算连续递增的子串长度 dp[p[i]]=max(dp[p[i]],k) 最后再将，以a,b,c..结尾的子串的最长长度相加，就是答案了
代码
func findSubstringInWraproundString(p string) (ans int) { dp := [26]int{} k := 0 for i, v := range p { if i > 0 && (v-int32(p[i-1])+26)%26==1 { k++ } else { k = 1 } dp[v-'a'] = max(dp[v-'a'], k) } for _, v := range dp { ans += v } return ans } func max(a, b int) int { if b > a { return b } return a }
