459.重复的子字符串

链接：459.重复的子字符串
难度：Easy
标签：字符串、字符串匹配
简介：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过 10000。

题解 1 - typescript

• 编辑时间：2020-08-24
• 执行用时：100ms
• 内存消耗：39.3MB
• 编程语言：typescript
• 解法介绍：获取每个子字符串进行判断

function repeatedSubstringPattern(s: string): boolean {
  const l = s.length;
  for (let i = 1; i < l; i++) {
    if (
      s[i - 1] === s[l - 1] &&
      l % i === 0 &&
      s.replace(new RegExp(s.substring(0, i), 'g'), '') === ''
    )
      return true;
  }
  return false;
}

题解 2 - typescript

• 编辑时间：2021-10-15
• 执行用时：80ms
• 内存消耗：44.7MB
• 编程语言：typescript
• 解法介绍：kmp。

function repeatedSubstringPattern(s: string): boolean {
  const next = [-1];
  const n = s.length;
  for (let i = 1, j = -1; i < n; i++) {
    while (j !== -1 && s[j + 1] !== s[i]) j = next[j];
    if (s[j + 1] === s[i]) j++;
    next[i] = j;
  }
  const idx = next[n - 1];
  return idx !== -1 && n % (n - idx - 1) === 0;
}