0686. 重复叠加字符串匹配

0686. 重复叠加字符串匹配 #

  • 标签:字符串、字符串匹配
  • 难度:中等

题目大意 #

描述:给定两个字符串 ab

要求:寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1

注意:字符串 "abc" 重复叠加 0 次是 "",重复叠加 1 次是 "abc",重复叠加 2 次是 "abcabc"

解题思路 #

假设字符串 a 的长度为 nb 的长度为 m

b 看做是模式串,把字符串 a 叠加后的字符串看做是文本串,这道题就变成了单模式串匹配问题。

我们可以模拟叠加字符串 a 后进行单模式串匹配问题。模拟叠加字符串可以通过在遍历字符串匹配时对字符串 a 的长度 n 取余来实现。

那么问题关键点就变为了如何高效的进行单模式串匹配,以及字符串循环匹配的退出条件是什么。

单模式串匹配问题:可以用 KMP 算法来做。

循环匹配退出条件问题:假设我们用 i 遍历 a 叠加后字符串,用 j 遍历字符串 b。如果字符串 ba 叠加后字符串的子串,那么 b 有两种可能:

  • b 直接是原字符串 a 的子串。
    • 这种情况下,最多遍历到 len(a)
  • ba 叠加后的字符串的子串。
    • 最多遍历到 len(a) + len(b),可以写为 while i < len(a) + len(b):,当 i == len(a) + len(b) 时跳出循环。
    • 也可以写为 while i - j < len(a):,这种写法中 i - j 表示的是字符匹配开始的位置,如果匹配到 len(a) 时(即 i - j == len(a) 时)最开始位置的字符仍没有匹配,那么 b 也不可能是 a 叠加后的字符串的子串了,此时跳出循环。

最后我们需要计算一下重复叠加字符串 a 的最小次数。假设 index 使我们求出的匹配位置。

  • 如果 index == -1,则说明 b 不可能是 a 叠加后的字符串的子串,返回 False
  • 如果 len(a) - index >= len(b),则说明匹配位置未超过字符串 a 的长度,叠加 1 次(字符串 a 本身)就可以匹配。
  • 如果 len(a) - index < len(b),则说明需要叠加才能匹配。此时最小叠加次数为 $\lfloor \frac{index + len(b) - 1}{len(a)} \rfloor + 1$。其中 index 代笔匹配开始前的字符串长度,加上 len(b) 后就是匹配到字符串 b 结束时最少需要的字符数,再 -1 是为了向下取整。 除以 len(a) 表示至少需要几个 a, 因为是向下取整,所以最后要加上 1。写成代码就是:(index + len(b) - 1) // len(a) + 1

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    # KMP 匹配算法,T 为文本串,p 为模式串
    def kmp(self, T: str, p: str) -> int:
        n, m = len(T), len(p)

        next = self.generateNext(p)

        i, j = 0, 0
        while i - j < n:
            while j > 0 and T[i % n] != p[j]:
                j = next[j - 1]
            if T[i % n] == p[j]:
                j += 1
            if j == m:
                return i - m + 1
            i += 1
        return -1

    def generateNext(self, p: str):
        m = len(p)
        next = [0 for _ in range(m)]

        left = 0
        for right in range(1, m):
            while left > 0 and p[left] != p[right]:
                left = next[left - 1]
            if p[left] == p[right]:
                left += 1
            next[right] = left

        return next

    def repeatedStringMatch(self, a: str, b: str) -> int:
        len_a = len(a)
        len_b = len(b)
        index = self.kmp(a, b)
        if index == -1:
            return -1
        if len_a - index >= len_b:
            return 1
        return (index + len(b) - 1) // len(a) + 1
本站总访问量  次  |  您是本站第  位访问者