golang力扣leetcode 467.环绕字符串中唯一的子字符串

• 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
}