[leetcode daily question] Repeat overlay string matching

Topic link

https://leetcode-cn.com/problems/repeated-string-match

Title Description

questions ： secondary

Given two strings  a and b, Look for overlapping strings a The minimum number of times , Make string b Becomes the superimposed string a The string of , Returns if it does not exist -1.

Be careful ： character string "abc"  Repeat stack 0 Next is "", Repeat stack 1 Next is  "abc", Repeat stack 2 Next is  "abcabc".

Their thinking

Python It's easy to match strings in , Call directly x.find(y) You can find it y stay x Position in .

But we need to put a Repeat the stack several times , only There may be Contains substrings b（ It may never include ）, So you can't stack indefinitely a, But to find a reasonable upper bound k , bring If a Repeat stack k Next time b Still not a substring , Then no matter how many times it is stacked , b It will never be a substring .

So the core here is to determine the upper bound k, There should be a GIF chart , That makes sense , But because of GIF Made with （ No ） some （ Meeting ） hemp （ system ） Bother （ do ）, So we can draw a conclusion directly ：

You can make len(a) * k >= len(a) + len(b) Established k It's all possible .

So just repeat the stack a, Until its length is greater than len(a) + len(b), And then call
.find() You can find it b Position in the stack string , This position can be used to determine how many times the stack can contain b.

# Python3
class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        res = len(b) // len(a) + 1
        temp = ''
        for _ in range(res):
            temp += a
        temp += a
        #  Found using after submission temp.find(b) Method takes time 84ms,
        #  The following direct traversal only needs 40ms, So use traversal instead 
        for i in range(len(temp) - len(b) + 1):
            if b == temp[i: i + len(b)]:
                x, y = divmod(i + len(b), len(a))
                if y > 0:
                    x += 1
                return x
        return -1
            return x
        return -1