java - Leetcode 686 重复字符串匹配无法理解解释

Question

我无法理解为什么 Leetcode 的重复字符串匹配的解决方案只能达到 A 的 q + 1 次重复(如果 A.length() < B.length())，因为 B 可能是 A 重复的子字符串.

我阅读了其他 StackOverflow 解决方案以及 Leetcode 讨论页面，但我仍然无法完全理解该解决方案。

算法解释为:

Imagine we wrote S = A+A+A+.... If B is to be a substring of S, we 
only need to check whether some S[0:], S[1:], ..., S[len(A) - 1:] 
starts with B, as S is long enough to contain B, and S has period 
at most len(A).

Now, suppose q is the least number for which len(B) <= len(A * q). 
We only need to check whether B is a substring of A * q or A * 
(q+1). If we try k < q, then B has larger length than A * q and 
therefore can't be a substring. When k = q+1, A * k is already big 
enough to try all positions for B; namely, A[i:i+len(B)] == B for i 
= 0, 1, ..., len(A) - 1.

实现如下:

class Solution {
  public int repeatedStringMatch(String A, String B) {
      int q = 1;
      StringBuilder S = new StringBuilder(A);
      for (; S.length() < B.length(); q++) S.append(A);
      if (S.indexOf(B) >= 0) return q;
      if (S.append(A).indexOf(B) >= 0) return q+1;
      return -1;
  }
}

我知道当 A.length() < B.length() 时，B 不能是子字符串，因此我们需要不断追加 A 直到 A.length() 至少等于 B.length()。但既然如此，为什么我们只需要再添加一份A就可以得到最少的重复次数呢？

我的直觉是，在 A 重复一定次数后，就会建立一个模式，如果 B 不属于该模式/字符序列，那么无论您重复 A 多少次，B 都不会是 a重复A的子串。

但是，我只是不知道为什么它必须具体是与 B 的长度匹配的副本数，或者在 A.length() = B.length() 之后添加 1 个副本。

如果有人能为我解决这个困惑，我将不胜感激。谢谢。

Answer 1

我想你已经基本明白其中的大部分内容了， 那么让您看另一个基本示例。

ampleex
itsalreadyhereexample
exam

假设 B 是示例，A 是上述之一。

<小时/>

对于第一种情况 A.length() == B.length()
我们检查它是否是一个子字符串，得到的答案是“否”。
所以我们再次添加它并得到'ampleexampleex'
现在我们得到 A 包含 B 的结果。

<小时/>

对于第二种情况 A.length() > B.length()
检查是否是子串，结果是A包含B。

(如果它不在这里，我们仍然需要检查它是否在重复中，
相当于第一种情况)

<小时/>

对于第三种情况 A.length() < B.length
所以我们重复直到我们覆盖 B 的长度
并获取examexam。

我们发现它不在那里，所以我们再次添加它，
但它仍然不在那里 (examexamexam)。

<小时/>

我们需要这样做的原因是因为它可能是更特殊的情况。
B 可以是类似 xamexame 的东西 - 基本上是一个重复 As 变体之一。

(这种情况下可能的变化是重复 xame、amex、mexa。)

在这种情况下，它必须是比 B 长的重复形式， 这就是 q+1 的来源。

让我们更详细地看看重复:
B的长度最多可以是(A.length()*q)+x，其中x是[0, A.length]。

A = exam
B = xame[xame]

B 仍然是 A 的重复，但最后一个重复中的每个字符都是可选的。

examexam
 xame
 xamex
 xamexa
 xamexam

examexamexam
 xamexame

向 S 添加另一个考试不会改变任何事情，因为我们已经涵盖了所有可能性(从现在开始不会出现新的模式)。

如果它不在那里，它就不可能是重复。其他场景 - 哪里 它可能是一个子字符串 - 已被第一种和第二种情况覆盖。

<小时/>

我希望通过这个例子可以帮助您消除困惑。 如果不明白就问你哪一点不明白。