📖字符串｜KMP

2024-7-20|2024-11-16
黎明
黎明
type
status
date
slug
summary
tags
category
icon
password
进度
解决什么问题❓术语 📖前缀📖后缀📖真前缀📖真后缀📖子串📖真子串📖字符串匹配📖参考文章 🔗

解决什么问题❓

对于文本字符串, 匹配模式串，匹配时间。
 

术语 📖

  • 空字符串
  • 前缀 prefix
  • 真前缀 proper prefix
  • 后缀 suffix
  • 真后缀 proper suffix
  • 暴力破解 Brude-Force
  • KMP Knuth-Morris-Pratt
 

前缀📖

给定字符串，若字符串是从首位置开始的任意长度的子字符串，则是的一个前缀。
示例：
所有前缀:
 

后缀📖

给定字符串，若字符串是从任意位置到末位置的任意长度的子字符串，则是的一个后缀。
示例：
所有后缀：
 

真前缀📖

给定字符串，若是前缀且不等于，则是的一个真前缀。
示例：
所有前缀:
 

真后缀📖

给定字符串，若是后缀且不等于，则是的一个真后缀。
示例：
所有后缀：
 

子串📖

给定字符串，若存在两个字符串，使得 ，则是的一个子串。
示例：
所有子串:
 

真子串📖

给定字符串，若是子串且不等于，则是的一个真子串。
示例：
所有子串:
 

字符串匹配📖

KMP算法核心思想：基于已匹配信息预先计算出必要信息
KMP算法核心思想：基于已匹配信息预先计算出必要信息
BF:
观察可知：发生不匹配时，回溯，重新匹配。
算法复杂度 。
 
KMP:
观察可知：发生不匹配时，不回溯，回退某个位置匹配。回退的位置可能有多个
选取最优：
算法复杂度
 
假设模式字符串与文本字符串匹配，是偏移量。对于满足条件的，使得最小。
 
  1. 由条件可知，的真前缀也是的后缀，即
  1. 由条件可知，，为使得最小，即求解最大值。
综上所述：
求的最大值，使得既是的真前缀，也是的后缀，即求的前缀函数。
注意理解的含义: 当不匹配时的已匹配的长度。
示例：; 红色表示不匹配位置，绿色表示已匹配长度。
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
不匹配时，
→
→
 
→
 
→
 
→
→
→
→
→
→
→
→
→
→
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
a
b
c
a
b
c
a
b
c
a
b
c
a
b
d
0
0
0
0
1
2
3
4
5
6
7
8
9
10
11
记：
  1. 若：，则
  1. 若：，则（等价于)不匹配；重新(1)(2)
 
前缀函数
 
 

参考文章 🔗

 
算法导论
后端开发｜设计模式动画｜Blender
Loading...