字符串 Part02 笔记#

151. 翻转字符串里的单词#

LeetCode 151. 翻转字符串里的单词

1
class Solution:
2
    def reverseWords(self, s: str) -> str:
3
        # 将字符串按空格分割成单词列表
4
        s = s.split()
5
        left, right = 0, len(s) - 1
6
        # 使用双指针反转单词列表
7
        while left < right:
8
            s[left], s[right] = s[right], s[left]
9
            left += 1
10
            right -= 1
11
        return ' '.join(s)

卡码网：55. 右旋转字符串#

题目链接

1
import sys
2
input = sys.stdin.read
3

4
# 右旋转字符串，当字符串长度小于旋转次数时，实际旋转次数为长度取模
5
def main():
6
    data = input().split()
7
    num = int(data[0])
8
    s = data[1]
9
    length = len(s)
10
    num = num % length
11
    res = []
12
    res.append(s[length - num:])
13
    res.append(s[:length - num])
14
    print(''.join(res))
15

16
if __name__ == "__main__":
17
    main()

KMP 算法#

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法。
通过构建 部分匹配表（前缀表），避免重复匹配字符，从而提升搜索效率。
时间复杂度：O(n + m)，其中 n 为文本串长度，m 为模式串长度。

应用场景#

✅ 在大文本中查找子串
- 最基础的用途，替代暴力匹配。
✅ 实现 strStr() 函数
- LeetCode 28，查找子串首次出现的位置。
✅ 检测字符串是否由重复子串组成
- LeetCode 459，判断字符串是否能通过子串重复构成。
✅ 字符串周期性检测
- 判断字符串的最小循环节，比如 DNA 重复序列。
✅ 最小字符串构造问题
- 构造最短的重复串，使得一个字符串成为其前缀或后缀。
✅ 前后缀匹配、构建自动机状态转移表
- KMP 中的 next 数组本质就是一种状态机转移的前缀优化，常用于构建有限状态机（FSM）模型。
✅ 字符串压缩 / 编码
- 如在数据压缩算法中，寻找重复模式进行压缩（与 Z-algorithm、Boyer-Moore 可组合）。
✅ 回文串构造与检测（改造版）
- 例：添加最少字符使字符串变为回文（可将 rev(s) + "#" + s 套用 KMP）。

KMP 算法模板#

1
# 获取模式串的前缀表（部分匹配表）
2
def getNext(s):
3
    next = [0]
4
    length = 0
5
    i = 1
6
    while i < len(s):
7
        if s[i] == s[length]:
8
            length += 1
9
            next.append(length)
10
            i += 1
11
        else:
12
            if length == 0:
13
                next.append(0)
14
                i += 1
15
            else:
16
                length = next[length - 1]
17
    return next
18

19
# 主函数，查找模式串在文本串中出现的位置
20
def strStr(string, pattern):
21
    next = getNext(pattern)
22
    i, j = 0, 0
23
    while i < len(string):
24
        if string[i] == pattern[j]:
25
            i += 1
26
            j += 1
27
        elif j > 0:
28
            j = next[j - 1]
29
        else:
30
            i += 1
31
    if j == len(pattern):
32
        return i - j
33
    return -1

28. 实现 strStr()#

LeetCode 28. 实现 strStr()

1
class Solution:
2
    def strStr(self, haystack: str, needle: str) -> int:
3
        next = self.getNext(needle)
4
        i, j = 0, 0
5
        while i < len(haystack):
6
            if haystack[i] == needle[j]:
7
                i += 1
8
                j += 1
9
                # 如果 j 达到 needle 的长度，说明找到了匹配
10
                if j == len(needle):
11
                    return i - j
12
            elif j > 0:
13
                j = next[j - 1]
14
            else:
15
                i += 1
16
        # 如果 j 没有达到 needle 的长度，说明没有找到匹配
17
        return -1
18

19
    def getNext(self, s):
20
        next = [0]
21
        length = 0
22
        i = 1
23
        while i < len(s):
24
            if s[i] == s[length]:
25
                length += 1
26
                next.append(length)
27
                i += 1
28
            else:
29
                if length == 0:
30
                    next.append(0)
31
                    i += 1
32
                else:
33
                    length = next[length - 1]
34
        return next

459. 重复的子字符串#

LeetCode 459. 重复的子字符串

1
class Solution:
2
    def repeatedSubstringPattern(self, s: str) -> bool:
3
        next = self.getNext(s)
4
        n = len(s)
5
        # 如果 next 数组的最后一个值大于 0，且 n 能被 n - next[-1] 整除，则说明存在重复的子字符串
6
        return next[-1] > 0 and n % (n - next[-1]) == 0
7

8
    def getNext(self, s):
9
        next = [0]
10
        length = 0
11
        i = 1
12
        while i < len(s):
13
            if s[length] == s[i]:
14
                i += 1
15
                length += 1
16
                next.append(length)
17
            else:
18
                if length == 0:
19
                    next.append(0)
20
                    i += 1
21
                else:
22
                    length = next[length - 1]
23
        return next