686 重复叠加字符串匹配（枚举、kmp匹配字符串）

阳光穿透心脏的1/2处 2022-09-03 04:15 125阅读 0赞

**1. 问题描述：**

给定两个字符串 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 <= 10 ^ 4  
1 <= b.length <= 10 ^ 4  
a 和 b 由小写英文字母组成  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/repeated-string-match

**2. 思路分析：**

首先字符串a的长度必须大于等于字符串b的长度，这样b才能够在a中出现，所以我们需要先复制k次a使得a的长度大于等于b的长度，然后从第一个位置开始枚举，判断从当前位置开始的长度为len(b)的字符串是否匹配字符串b，不匹配再枚举下一个位置，由于a是由若干次a复制得到的所以第二段与第一段是完全相同的，所以我们不必要枚举所有的位置（第二段与第一段的枚举的字符串都是一样的），我们只需要枚举第一段a的所有位置作为匹配的开始位置即可，为了可以匹配第一段a最后一个字符开始的字符串，所以我们需要在a的末尾再加上额外的一段a，如果在a的第一段中的所有位置都找不到b说明之后的位置也不可能找到b，所以a中不存在这样的串能够匹配字符串b。这样问题就变为判断在复制若干次得到字符串a中是否存在字符串b即可，在一个串中匹配另外一个字符串是否存在可以使用[kmp][]算法，默写出**kmp算法**的模板即可。

**3. 代码如下：**

class Solution:
        def repeatedStringMatch(self, a: str, b: str) -> int:
            s = ""
            while len(s) < len(b):
                s += a
            # 加上需要最后一段a
            s += a
            # 下面使用kmp算法匹配字符串b是否在字符串a中
            n = len(s)
            m = len(b)
            s = " " + s
            p = " " + b
            next = [0] * (m + 1)
            i, j = 2, 0
            # 求解next数组
            while i <= m:
                while j and p[i] != p[j + 1]: j = next[j]
                if p[i] == p[j + 1]: j += 1
                next[i] = j
                i += 1
            # 匹配b是否在a中
            i, j = 1, 0
            while i <= n:
                while j and s[i] != p[j + 1]: j = next[j]
                if s[i] == p[j + 1]: j += 1
                # 找到了a中的子串, 当前i的位置判断需要多少个a, 这个时候就需要i / len(a)向上取整
                # a / k向上取整等于 (a + k - 1) / k向下取整
                if j == m: return (i + len(a) - 1) // len(a)
                i += 1
            return -1

[kmp]: https://blog.csdn.net/qq_39445165/article/details/118500142