时间戳

首页 > 解决方案 > 重复字符串匹配 Leetcode

python - 重复字符串匹配 Leetcode

问题描述

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

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

返回 3，因为通过重复 A 三次（“abcdabcdabcd”），B 是它的子串；并且 B 不是 A 的子串重复两次（“abcdabcd”）。

注意：A 和 B 的长度在 1 到 10000 之间。

解决方案有这样的解释：

现在，假设 q 是 len(B) <= len(A * q) 的最小数。我们只需要检查 B 是 A * q 还是 A * (q+1) 的子串。如果我们尝试 k < q，那么 B 的长度大于 A * q，因此不能是子字符串。当 k = q+1 时​​，A * k 已经大到可以为 B 尝试所有位置；即，A[i:i+len(B)] == B 对于 i = 0, 1, ..., len(A) - 1。

我无法理解 q+1 的情况。如果 q 是将 B 作为子字符串的最小数字，而不是为什么在代码中我们必须检查 q + 1 的情况。

很久以前有人发的问题。 重复字符串匹配

标签： pythonalgorithm

解决方案

举个例子：A =“abcd”和B =“cdabcdab”。然后len(B) = 8和len(A) = 4。因此，q = 2。但是A * 2 = abcdabcd，soB不是子字符串。因此，您也需要检查A * 3 = abcdabcdabcd。

请注意，这q不是 的B子串的最小数目A*q，而是len(B) <= len(A*q)成立的最小数目。

推荐阅读