leetcode-go/leetcode/hard/466.count-the-repetitions.go

func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
	// dp[i][k] = dp[i][k-1] + dp[(i+dp[i][k-1])%m][k-1], m = len(s1)
	// dp[i][k] means the length required to match 2^k of s2
	// from the ith char of s1.
	m, n := len(s1), len(s2)
	r1, r2 := []rune(s1), []rune(s2)
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, 31) // 2^30 is the limit, cauz MaxInt32 < 2^31
	}
	for i := 0; i < m; i++ {
		l1, l2 := i, 0
		for l2 < n { // Match 2^0 of s2
			for l1 < n1*m && r1[l1%m] != r2[l2] {
				l1++
			}
			l1, l2 = l1+1, l2+1
		}
		dp[i][0] = l1 - i
	}
	for k := 1; k < 31; k++ {
		for i := 0; i < m; i++ {
			dp[i][k] = dp[i][k-1] + dp[(i+dp[i][k-1])%m][k-1]
		}
	}
	ans := int64(0)
	beg := 0
	for k := 30; 0 <= k; k-- {
		for beg+dp[beg%m][k] <= n1*m {
			ans += 1 << uint(k)
			beg += dp[beg%m][k]
		}
	}
	return int(ans) / n2
}