第4章串

串是特殊的线性表，每个数据元素是一个字符。字符串匹配是计算机科学中的经典问题，朴素匹配简单但效率低，KMP算法通过预处理模式串实现高效匹配。

1. 朴素模式匹配（BF算法）

核心思想：从主串的每个位置开始，依次与模式串比较。匹配失败时，主串指针向后移一位，模式串指针重置为0，重新开始比较。

时间复杂度：

最好：O(n)（模式串在主串开头就匹配）
最坏：O(m×n)（每个位置都要比较到模式串末尾才失败）

匹配过程（手写示例）

主串: "ABABCABCABABCD" (n=13) 模式串: "ABCAB" (m=5)

第1轮 i=0:
  主串:  A B A B C A B C A B A B C D
  模式:  A B C A B
  比较:  A==A, B==B, A!=C ✗ 失败！

第2轮 i=1:
  主串:  A B A B C A B C A B A B C D
  模式:    A B C A B
  比较:  B==A ✗ 失败！

第3轮 i=2:
  主串:  A B A B C A B C A B A B C D
  模式:      A B C A B
  比较:  A==A, B==B, C==C, A==A, B==B ✓ 匹配成功！

返回: 2

Python实现

python

def naive_match(text: str, pattern: str) -> int:
    """
    朴素模式匹配（BF算法）
    返回pattern在text中的起始位置，未找到返回-1

    时间复杂度: O(m×n), m为模式串长度，n为主串长度
    空间复杂度: O(1)
    """
    n, m = len(text), len(pattern)

    # 遍历主串的所有可能起始位置
    for i in range(n - m + 1):
        j = 0  # 模式串指针

        # 依次比较字符
        while j < m and text[i + j] == pattern[j]:
            j += 1

        # j==m 表示模式串全部匹配成功
        if j == m:
            return i

    return -1  # 未找到

2. KMP算法

核心思想：利用已经部分匹配的有效信息，主串指针不回溯，通过修改模式串指针，让模式串尽量移动到有效位置。

关键优化：当匹配失败时，主串指针i不回溯，模式串指针j回退到next[j]位置，而不是回退到0。

next数组含义

next[j] 表示：当模式串第j个字符匹配失败时，模式串指针应该回退到的位置。

数学定义：next[j] 等于模式串 pattern[0:j] 的最长相等前后缀长度（不包括自身）。

前缀和后缀：

前缀：从开头到某位置（不包括整个串）
后缀：从某位置到结尾（不包括整个串）

手工计算next数组

模式串: "ABABC"

j	pattern[0:j]	前缀	后缀	最长相等前后缀	next[j]
0	`""`	-	-	-	-1
1	`"A"`	-	-	无	0
2	`"AB"`	`"A"`	`"B"`	无	0
3	`"ABA"`	`"A"`, `"AB"`	`"BA"`, `"A"`	`"A"`	1
4	`"ABAB"`	`"A"`, `"AB"`, `"ABA"`	`"BAB"`, `"AB"`, `"B"`	`"AB"`	2
5	`"ABABC"`	`"A"`, `"AB"`, `"ABA"`, `"ABAB"`	`"BABC"`, `"ABC"`, `"BC"`, `"C"`	无	0

next数组: [-1, 0, 0, 1, 2, 0]

next数组计算过程

模式串: "ABABC"

j=0, k=-1: next[0]=-1

j=1, k=-1: k==-1, j++, k++
         next[1]=0

j=2, k=0:  pattern[2]='C' != pattern[0]='A'
         k=next[k]=-1
j=2, k=-1: k==-1, j++, k++
         next[2]=0

j=3, k=0:  pattern[3]='A' == pattern[0]='A'
         j++, k++, next[3]=1

j=4, k=1:  pattern[4]='B' == pattern[1]='B'
         j++, k++, next[4]=2

j=5, k=2:  j==m 结束

结果: next = [-1, 0, 0, 1, 2, 0]

KMP匹配过程（手写示例）

主串: "ABABCABCABABCD"模式串: "ABCAB"next数组: [-1, 0, 0, 1, 2, 0]

初始 i=0, j=0:
  主串:  A B A B C A B C A B A B C D
  模式:  A B C A B
  i=0, j=0: A==A, i++, j++

i=1, j=1:
  主串:  A B A B C A B C A B A B C D
  模式:  A B C A B
  i=1, j=1: B==B, i++, j++

i=2, j=2:
  主串:  A B A B C A B C A B A B C D
  模式:  A B C A B
  i=2, j=2: A!=C ✗ 失败！
  j=next[2]=0 (模式串指针回退)

i=2, j=0:
  主串:  A B A B C A B C A B A B C D
  模式:      A B C A B
  i=2, j=0: A==A, i++, j++

i=3, j=1:
  主串:  A B A B C A B C A B A B C D
  模式:      A B C A B
  i=3, j=1: B==B, i++, j++

i=4, j=2:
  主串:  A B A B C A B C A B A B C D
  模式:      A B C A B
  i=4, j=2: C==C, i++, j++

i=5, j=3:
  主串:  A B A B C A B C A B A B C D
  模式:      A B C A B
  i=5, j=3: A==A, i++, j++

i=6, j=4:
  主串:  A B A B C A B C A B A B C D
  模式:      A B C A B
  i=6, j=4: B==B, i++, j++

j==5 (m) ✓ 匹配成功！
返回 i-j = 6-5 = 1

Python实现

python

def compute_next(pattern: str) -> list:
    """
    计算next数组
    next[j]表示当pattern[j]匹配失败时，应该回退到的位置

    时间复杂度: O(m)
    空间复杂度: O(m)
    """
    m = len(pattern)
    next_arr = [-1] * m
    i, j = 0, -1  # i当前计算位置，j前缀匹配位置

    while i < m - 1:
        if j == -1 or pattern[i] == pattern[j]:
            # 匹配成功，i和j都前进
            i += 1
            j += 1
            next_arr[i] = j
        else:
            # 匹配失败，j回退到next[j]
            j = next_arr[j]

    return next_arr


def kmp_match(text: str, pattern: str) -> int:
    """
    KMP模式匹配
    返回pattern在text中的起始位置，未找到返回-1

    时间复杂度: O(m+n), m为模式串长度，n为主串长度
    空间复杂度: O(m) 存储next数组
    """
    if not pattern:
        return 0

    n, m = len(text), len(pattern)
    next_arr = compute_next(pattern)

    i, j = 0, 0  # i指向text，j指向pattern

    while i < n and j < m:
        if j == -1 or text[i] == pattern[j]:
            # 匹配成功或j==-1（重置），两个指针都前进
            i += 1
            j += 1
        else:
            # 匹配失败，主串指针i不回溯，模式串j回退
            j = next_arr[j]

    # j==m 表示模式串全部匹配
    if j == m:
        return i - j
    return -1


if __name__ == "__main__":
    text = "ABABCABCABABCD"
    pattern = "ABCAB"

    print(f"主串: {text}")
    print(f"模式串: {pattern}")
    print(f"next数组: {compute_next(pattern)}")
    print(f"匹配位置: {kmp_match(text, pattern)}")

3. 考研重点 & 易错点

高频考点

考点	关键要点
next数组计算	最长相等前后缀长度，必须手工计算
KMP vs 朴素	KMP主串不回溯，时间复杂度O(m+n)
next数组定义	有的版本next[0]=-1，有的next[0]=0
nextval数组	nextval优化避免重复比较

易错点

易错点	正确做法
next数组定义	注意题目要求的版本（-1或0开头）
KMP主串指针	匹配失败时i不回溯，只有j回退
next数组计算	最长相等前后缀，不包括整个串本身
时间复杂度	KMP是O(m+n)，朴素是O(m×n)

手工计算技巧

写出模式串的每个前缀
对每个前缀，列出所有可能的前缀和后缀
找最长相等的前缀和后缀
长度即为next值

快速计算示例："ABAB"

前缀"ABAB": 前缀={A,AB,ABA}, 后缀={BAB,AB,B}
最长相等前后缀: "AB" (长度2)
所以next[4] = 2

4. 复杂度对比表

算法	时间复杂度	空间复杂度	特点
朴素匹配	O(m×n)	O(1)	简单直观，效率低
KMP预处理	O(m)	O(m)	预处理next数组
KMP匹配	O(n)	O(m)	主串不回溯
KMP总计	O(m+n)	O(m)	高效算法

5. next数组优化（nextval）

核心思想：当 pattern[j] == pattern[next[j]] 时，回退到next[j]仍然会失败，直接回退到next[next[j]]。

示例：模式串 "AAA"

j	pattern[j]	next[j]	nextval[j]
0	A	-1	-1
1	A	0	-1 (A==A，取next[0])
2	A	1	-1 (A==A，取nextval[1])

优势：减少不必要的比较。

python

def compute_nextval(pattern: str) -> list:
    """计算优化后的nextval数组"""
    m = len(pattern)
    next_arr = compute_next(pattern)
    nextval = [-1] * m

    for j in range(1, m):
        if pattern[j] == pattern[next_arr[j]]:
            nextval[j] = next_arr[next_arr[j]]
        else:
            nextval[j] = next_arr[j]

    return nextval

📝 完整代码示例

python

def naive_match(text: str, pattern: str) -> int:
    """朴素模式匹配"""
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i
    return -1


def compute_next(pattern: str) -> list:
    """计算next数组"""
    m = len(pattern)
    next_arr = [-1] * m
    i, j = 0, -1
    while i < m - 1:
        if j == -1 or pattern[i] == pattern[j]:
            i += 1
            j += 1
            next_arr[i] = j
        else:
            j = next_arr[j]
    return next_arr


def kmp_match(text: str, pattern: str) -> int:
    """KMP模式匹配"""
    if not pattern:
        return 0
    n, m = len(text), len(pattern)
    next_arr = compute_next(pattern)
    i, j = 0, 0
    while i < n and j < m:
        if j == -1 or text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = next_arr[j]
    return i - j if j == m else -1


if __name__ == "__main__":
    text = "ABABCABCABABCD"
    pattern = "ABCAB"

    print("=" * 40)
    print(f"主串: {text}")
    print(f"模式串: {pattern}")
    print("=" * 40)

    print("\n【朴素匹配】")
    pos_naive = naive_match(text, pattern)
    print(f"匹配位置: {pos_naive}")

    print("\n【KMP算法】")
    next_arr = compute_next(pattern)
    print(f"next数组: {next_arr}")
    pos_kmp = kmp_match(text, pattern)
    print(f"匹配位置: {pos_kmp}")

    print("\n【复杂度对比】")
    print(f"朴素匹配: O(m×n) = O({len(pattern)}×{len(text)}) = O({len(pattern) * len(text)})")
    print(f"KMP算法: O(m+n) = O({len(pattern)}+{len(text)}) = O({len(pattern) + len(text)})")

第4章 串 ​

1. 朴素模式匹配（BF算法） ​

匹配过程（手写示例） ​

Python实现 ​

2. KMP算法 ​

next数组含义 ​

手工计算next数组 ​

next数组计算过程 ​

KMP匹配过程（手写示例） ​

Python实现 ​

3. 考研重点 & 易错点 ​

高频考点 ​

易错点 ​

手工计算技巧 ​

4. 复杂度对比表 ​

5. next数组优化（nextval） ​

📝 完整代码示例 ​

第4章串

1. 朴素模式匹配（BF算法）

匹配过程（手写示例）

Python实现

2. KMP算法

next数组含义

手工计算next数组

next数组计算过程

KMP匹配过程（手写示例）

Python实现

3. 考研重点 & 易错点

高频考点

易错点

手工计算技巧

4. 复杂度对比表

5. next数组优化（nextval）

📝 完整代码示例