題目

由 n 個(gè)連接的字符串 s 組成字符串 S，記作 S = [s,n]。例如，["abc",3]=“abcabcabc”。

如果我們可以從 s2 中刪除某些字符使其變?yōu)?s1，則稱字符串 s1 可以從字符串 s2 獲得。例如，根據(jù)定義，"abc" 可以從 “abdbec” 獲得，但不能從 “acbbe” 獲得。

現(xiàn)在給你兩個(gè)非空字符串 s1 和 s2（每個(gè)最多 100 個(gè)字符長）和兩個(gè)整數(shù) 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106?，F(xiàn)在考慮字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。

請(qǐng)你找出一個(gè)可以滿足使[S2,M] 從 S1 獲得的最大整數(shù) M 。

示例：

輸入：
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2

返回：
2

思路:

示例中 S1 = "acbacbacbacb", S2 = "abab", 要使得[S2, M], 能從S1獲得, 即求 S2 在 S1中得字符最少得倍數(shù),即M

解法一: 暴力破解, 雙重循環(huán), 時(shí)間復(fù)雜度 O(n^2)

解法二: 找出除開頭符合的S2, 在找到剩下重復(fù)字段符合S2的字段長度, 剩余字段的總長度除以符合的長度取模即 剩下的值, 時(shí)間復(fù)雜度 O(s1 * s2)

code

按解法二解

go

// 耗時(shí)0ms
func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
    len1, len2 := len(s1), len(s2)
    index1, index2 := 0, 0 // s1, s2 的下標(biāo)

    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 { // 遍歷整個(gè) S1
        if index1%len1 == len1-1 { //在 S1 末尾
            if val, ok := map1[index2%len2]; ok {
                cycleLen := index1/len1 - val/len1                 // 每個(gè)循環(huán)占多少個(gè) S1
                cycleNum := (n1 - 1 - index1/len1) / cycleLen      // 還有多少個(gè)循環(huán)
                cycleS2Num := index2/len2 - map2[index2%len2]/len2 // 每個(gè)循環(huán)含有多少個(gè) 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
}