686.重复叠加字符串匹配

LeetCode - 重复叠加字符串匹配(中等) 题目出得很好，下次不要再出了

686. 重复叠加字符串匹配

难度中等206
给定两个字符串 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

提示：

• 1 <= a.length <= 104
• 1 <= b.length <= 104
• a 和 b 由小写英文字母组成

翻译一下

这道题的意思就是有无一个最小次数n，令a重复n次之后，使得b成为a的子串。举个栗子：

const a = 'abcd'
const b = 'cdabcdab'
//根据题意，a重复一次为本身(abcd),重复2次为abcdabcd,下面用c来表示
const c = 'abcdabcd' //很明显可以看出c还不足以 “包容” b
//重复三次，得到abcdabcdabcd
const d = 'abcdabcdabcd' //很明显可以看出d "包含" b

根据上面的代码，可以看出重复三次之后的a **包容** b，即：**abcdabcdabcd。**

思路

如果存在a重复n次之后的字符串包容b的现象，那么无非就是b的开头和结尾的字符串是a或者是a的一部分，即：
我们令 a’ = a | a的一部分 | null
那么 b = a’[a*(n-2)]a’

此时我们即刻推断出一个循环终止的条件了：要令这个n最小，毫无疑问是上述公式[a*(n-2)]的部分最好是用到b本身。
由此可以推断出a经过重复过后得到的新字符串具有长度小于 2 * a.length + b.length的特点。

代码

/**
 * @param {string} a
 * @param {string} b
 * @return {number}
 *
 * a重复最少次数使得b成为a的子串
 */
var repeatedStringMatch = function (a, b) {
  if (a === b) {
    return 1;
  }
  const a_length = a.length;
  const b_length = b.length;
  const max_length = 2 * a_length + b_length;
  let t = 0;
  let a_copy = a;
  while (a_copy.length < max_length) {
    if (a_copy.indexOf(b) !== -1) {
      return t;
    } else {
      t += 1;
      a_copy += a;
    }
  }
  return -1;
};