重复叠加字符串匹配

题目

题目来源：力扣（LeetCode）

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意：字符串 “abc” 重复叠加 0 次是 “”，重复叠加 1 次是 “abc”，重复叠加 2 次是 “abcabc”。

示例 1：

输入：a = “abcd”, b = “cdabcdab”
输出：3
解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。

示例 2：

输入：a = “a”, b = “aa”
输出：2

示例 3：

输入：a = “a”, b = “a”
输出：1

示例 4：

输入：a = “abc”, b = “wxyz”
输出：-1

思路分析

这题最关键的是找到循环退出条件，循环终止条件就是 累积的字符串长度S > (n + 2) A.length = (B.length/A.length + 2) A.length= B.length + 2 * A.length。

在B的长度大于A长度时且能够满足题意A叠加后B成为其子串的，总共只有四种情况：

• 叠加n个A后刚好与B完全相等，例如A = ‘ab’, B = ‘abab’，此时刚好只需要循环n次即可满足条件，循环更多次也只是重复无用功。
• 叠加n个A后与B的后部分完全相等，但此时B头部还有一小部分值刚好是A尾部分，例如A = ‘ab’, b = ‘babab’，此时最少需要循环n + 1次才可满足条件。
• 同上一条，但多余部分出现在B的尾部，例如A = ‘ab’, b = ‘ababa’，此时最少需要的循环次数同上。
• 同上，多余部分在B的头尾都有，例如A = ‘ab’, b = ‘bababa’，此时最少需要的循环次数为n + 2次。

由上面的所有情况分析得到最少需要循环的次数为n + 2次，n为正整数，转化为最小需要的长度S就是S >= (n + 2) A.length，因为 n = B.length / A.length，所以S >= B.length + 2 A.length 。

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 */
var repeatedStringMatch = function (A, B) {
  const bLen = B.length + A.length * 2;
  for (let count = 1, repeatA = A; repeatA.length <= bLen; count++, repeatA += A) {
    if (repeatA.includes(B)) return count;
  }
  return -1;
};