重复字符串匹配

本文介绍了重复字符串匹配的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I did Contest 52 of leetcode 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).

因此，如果完全适合，则必须在 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.)