字符串匹配:本身是指在一个字符串中找到另一个字符串,可以暴力的方式按照字符来进行匹配。优化匹配的效率的方向是:减少不成功的匹配次数,比如KMP、BM等优化策略都是如此,通过某种方式,或者某种规则来加速匹配过程。
BF算法(暴力算法)
普通模式的匹配算法:两个循环嵌套进行匹配,直到匹配成功。
Golang语法下可以截取字符串进行比较:
1 | // Golang语法字符串截取优化 |
1 | // BF算法:暴力算法 |
RK算法(基于BF算法的改进)
核心思想是哈希,即在详细比较之前,先使用hash进行比较,如果不匹配则右移。如果匹配,由于hash值可能存在碰撞的情况,因此需要进行详细判断。
1 | // RK算法:使用hash匹配匹配进行优化 |
KMP算法
关键在于部分匹配表(RMT表):字符串起始位置到当前位置的字符串,“前缀”和“后缀”的最长的共有元素长度。
移动位数 = 已匹配的字符数 - 对应的部分匹配值
。
部分匹配表代表:模式串中某个位置匹配失败的时候,可以直接转到某个位置开始重新开始匹配。
1 | // KMP算法:部分匹配表,在匹配失败时,可以跳过部分字符匹配 |
BM算法
从后往前对模式串进行扫描与主串进行匹配的,使用两个启发策略。
坏字符算法:坏字符:字符串中的某个字符跟模式串的某个字符不匹配时,这个失配字符为坏
字符。
- 模式串中有对应的坏字符时,让模式串最靠右的对应字符与坏字符相对。
- 模式串中不存在坏字符,那么直接右移整个模式串长度这么大步数。
坏字符表的定义为:对于输入字符集合中的字符C,如果C不在模式串中,则C对应的值=模式串最末元素的索引值-字符C在模式串中最右出现的位置
,字符不在模式串中时对应的值为-1。
好后缀算法:
- 模式串中有子串和好后嘴完全匹配,则将最靠右的那个子串移动到好后缀的位置继续进行匹配。
- 如果不存在和好后缀完全匹配的子串,则好后缀中找到具有如下特征的最长子串,使得
P[m-s...m] = P[0...s]
。 - 如果完全不存在和好后缀匹配的子串,则右移整个模式串。
1 | func MatchBM(str string, target string) int { |
Sunday算法
从前往后扫描模式串的,其思路更像是对于“坏字符”策略的升华,关注的是主串中参与匹配的最末字符的下一位,将其与当前跳表判断下一步移动距离。
启发策略:
- 当遇到不匹配的字符时,如果关注的字符没有在模式串中出现则直接跳过即
移动位数=子串长度+1
。 - 当遇到不匹配的字符时,如果关注的字符在模式串中也存在时,其
移动位数=模式串长度-该字符最右出现的位置(以0开始)
或者移动位数=模式串中该子串最右出现的位置到尾部的距离+1
。
1 | func MatchSunday(str string, target string) int { |