暴力匹配算法
首先呢先展示一下万能的暴力匹配算法,它的思想最简单,只是时间复杂度高了那么一点点,不过问题不大。
算法思想:
从主串的第一个字符起,与模式串的第一个字符比较,若相等,则继续逐个比较后续字符;否则从主串的下一个字符起,重新和模式串的字符比较;以此类推,直至模式串中的每个字符依次和主串中的一个连续的字符序列相等,则称匹配成功,函数值为与模式串中第一个字符相等的字符在主串中的序号,否则称匹配不成功,函数值为-1。
代码:
1 | // 暴力匹配算法 |
KMP算法
求next数组
PM表
字符串的前缀、后缀和部分匹配值
- 前缀:是指除最后一个字符外,字符串的所有头部子串。
- 后缀:是指除第一个字符外,字符串的所有尾部子串。
- 部分匹配值:字符串的前缀和后缀的最长相等前后缀长度。
以ababa
为例说明:
子串 | 前缀 | 后缀 | 最长相等的前后缀长度 |
---|---|---|---|
a | 无 | 无 | 0 |
ab | a | b | 0 |
aba | a,ab | a,ba | 1 |
abab | a,ab,aba | b,ab,bab | 2 |
ababa | a,ab,aba,abab | a,ba,aba,baba | 3 |
故字符串ababa
的部分匹配值为00123。
将部分匹配值写成数组形式就得到了部分匹配值表,PM表
下标 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
val | a | b | a | b | a |
PM | 0 | 0 | 1 | 2 | 3 |
将pm表右移一位就等到了next数组,左边的空缺用-1来填充。
下标 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
val | a | b | a | b | a |
next | -1 | 0 | 0 | 1 | 2 |
数据结构书上的字符串下标是从1开始的,实际编程中下标是从0开始,所以稍微有些出入
以下用代码来求next数组
1 | // 以-1开始 |
实现KMP
1 | public static int indexKMP(String text, String pattern) { |
__END__

文章作者:三国小梦
文章出处:字符串模式匹配kmp算法总结
作者签名:简单地活着, 肆意又精彩.
关于主题:Hexo - Live For Code
版权声明:文章除特别声明外,均采用 BY-NC-SA 许可协议,转载请注明出处
文章出处:字符串模式匹配kmp算法总结
作者签名:简单地活着, 肆意又精彩.
关于主题:Hexo - Live For Code
版权声明:文章除特别声明外,均采用 BY-NC-SA 许可协议,转载请注明出处