题目

由 n 个连接的字符串 s 组成字符串 S,记作 S = [s,n]。例如,[“abc”,3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。例如,根据定义,”abc” 可以从 “abdbec” 获得,但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2(每个最多 100 个字符长)和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2,其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。

示例:

输入:
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2

返回:
2
`

思路:

示例中 S1 = “acbacbacbacb”, S2 = “abab”, 要使得[S2, M], 能从S1获得, 即求 S2 在 S1中得字符最少得倍数,即M

解法一: 暴力破解, 双重循环, 时间复杂度 O(n^2)

解法二: 找出除开头符合的S2, 在找到剩下重复字段符合S2的字段长度, 剩余字段的总长度除以符合的长度取模即 剩下的值, 时间复杂度 O(s1 * s2)

code

按解法二解

go

// 耗时0ms
func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
	len1, len2 := len(s1), len(s2)
	index1, index2 := 0, 0 // s1, s2 的下标

	if len1 == 0 || len2 == 0 || len1*n1 < len2*n2 {
		return 0
	}

	map1, map2 := make(map[int]int), make(map[int]int)
	ans := 0
	
	for index1/len1 < n1 { // 遍历整个 S1
		if index1%len1 == len1-1 { //在 S1 末尾
			if val, ok := map1[index2%len2]; ok {
				cycleLen := index1/len1 - val/len1                 // 每个循环占多少个 S1
				cycleNum := (n1 - 1 - index1/len1) / cycleLen      // 还有多少个循环
				cycleS2Num := index2/len2 - map2[index2%len2]/len2 // 每个循环含有多少个 S2

				index1 += cycleNum * cycleLen * len1
				ans += cycleNum * cycleS2Num
			} else { 
				map1[index2%len2] = index1
				map2[index2%len2] = index2
			}

		}

		if s1[index1%len1] == s2[index2%len2] {
			if index2%len2 == len2-1 {
				ans += 1
			}
			index2 += 1
		}
		index1 += 1
	}
	return ans / n2
}