查找字符串 A 需要声明多少次才能包含字符串 B 作为子字符串的算法

Question

对于这个问题，我还没有想出一个可靠的答案。我的解决方案在少数情况下失败。我将不胜感激。

问题:

给定两个字符串 A 和 B，返回包含字符串 B 的 A 需要被声明的次数？

示例#1:

• 字符串 A : abcd
• 字符串 B : cdabcdab

应该返回 3 因为:

• abcdabcdabcd(A重复3次)
• cdabcdab(现在包含B)

示例#2:

• 字符串 A = abcd
• 字符串 B = d

应该返回 1，因为 B 已经是 A 的子串。

示例 #3:

• 字符串 A = abcd
• 字符串 B = cda

应该返回 2 因为:

• abcdabcd
• cda

示例 #4:

• 字符串 A = abcd
• 字符串 B = cdb

应该返回-1，无论我们说多少次A，我们都不可能产生B。

我注意到的一些见解:

1. 字符顺序很重要
2. A 必须至少包含所有B中的字符
3. A 或 B 都不需要是其他。
4. 一个字符串的末尾和另一个的开始。

Answer 1

如果|B| > 2|一个| - 2 和 B 出现在 A^n 中，然后 A 出现在 B 中。计算并删除 B 中 A 的所有完整实例，然后解决方案是此计数加上从 B 中删除 A 的相同问题的解决方案。

否则，保证如果B出现在A^n中，它就出现在A^3中。构造 A^3 并在其中找到 B 的第一次出现。查找并删除在 A^3 中 B 出现结束后出现的 A 的任何完整实例。返回 3 减去移除实例的数量。

例子:

f(abcd, cdabcdab)
|cdabcdab| > 2|abcd| - 2 since 8 > 2*4 - 2
   ^^^^
   first instance of A in B; no more, so return 1 + f(cdab, abcd) = 3
f(cdab, abcd)
|cdab| < 2|abcd| - 2 since 4 < 2*4 - 2
abcdabcdabcd
  ^^^^
  first instance of B in A; one instance of A after B, so return 3 - 1 = 2.

f(d, abcd)
|d| < 2|abcd| - 2, since 1 < 2*4 - 2
abcdabcdabcd
   ^
   first instance of B in A; two instances of A after B, so return 3 - 2 = 1.

f(cda, abcd)
|cda| = 2|abcd| - 2 since 3 = 2*4 - 2
abcdabcdabcd
  ^^^
  first instance of B in A; one instance of A after B, so return 3 - 1 = 2.

f(cdb, abcd)
|cbd| = 2|abcd| - 2 since 3 = 2*3 - 2
abcdabcdabcd
            ^ no instances of B in A; return -1.

一些小的优化包括:

• 如果|B| = 0，返回 0。
• 如果|B| = 1，用 A^1 代替 A^3。
• 如果|B| < |一个| + 2，用 A^2 代替 A^3。