重复字符串匹配 [英] Repeated String Match

问题描述

我参加了leetcode.com的第52场竞赛，但对理解解决方案有困难。问题语句为：

I did Contest 52 of leetcode.com and I had trouble understanding the solution. The problem statement is:

给出两个字符串A和B，找出必须重复执行A的最小次数，使得B为它的一个子串。如果没有这样的解决方案，则返回-1。

Given two strings A and B, find the minimum number of times A has to be >repeated such that B is a substring of it. If no such solution, return -1.

例如，以A = abcd和B = cdabcdab。

For example, with A = "abcd" and B = "cdabcdab.

返回3，因为重复3次（ abcdabcdabcd），B是它的>子字符串；而B不是重复2次
（ abcdabcd）的A的子字符串。

Return 3, because by repeating A three times ("abcdabcdabcd"), B is a >substring of it; and B is not a substring of A repeated two times ("abcdabcd").

解决方案是：

def repeatedStringMatch(self, A, B):
      """
      :type A: str
      :type B: str
      :rtype: int
      """
      times = int(math.ceil(float(len(B)) / len(A)))
      for i in range(2):
        if B in (A * (times + i)):
          return times + i
      return -1

说明来自其中一位合作者的信息：

The explanation from one of the collaborators was:

A必须重复足够的时间，使得其至少与> B一样长（或更多），因此我们可以得出结论：答案的理论下限>是B的长度/

A has to be repeated sufficient times such that it is at least as long as >B (or one more), hence we can conclude that the theoretical lower bound >for the answer would be length of B / length of A.

让x为理论下界，即ceil（len（B）/ len（A））。

Let x be the theoretical lower bound, which is ceil(len(B)/len(A)).

答案n只能是x或x + 1

The answer n can only be x or x + 1

我不明白为什么n只能是x或x + 1，有人可以帮忙吗？

I don't understand why n can only be x or x+1, can someone help?

推荐答案

如果 x + 1< n 并且B是A的子字符串，重复了 n 次，并且您已经在其中嵌入了B，那么您可以砍掉A的最后一个副本而不打B（意味着 n 不是最小的），否则A中B的开始是在第一份副本的结尾之后，因此您可以将第一份副本砍掉（并且再次 n 并非最小）。

If x+1 < n and B is a substring of A repeated n times and you've embedded B in it then either you can chop off the last copy of A without hitting B (meaning that n is not minimal) or else the start of B in A is after the end of the first copy so you can chop off the first copy (and again n is not minimal).

因此，如果完全适合，则必须在<$ c $以内c> x + 1 个副本。仅基于长度，它就不能容纳在< x 个副本。因此，剩下的唯一可能性是 x 和 x + 1 副本。 （示例可以在哪里找到答案）。

Therefore if it fits at all, it must fit within x+1 copies. Based on length alone it can't fit within < x copies. So the only possibilities left are x and x+1 copies. (And examples can be found where each is the answer.)

这篇关于重复字符串匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！