根据袁厨的算法小屋字符串匹配部分做的笔记
BF（Brute Force）
暴力匹配，所谓暴力就是不考虑性能要求，从主串的第0个字符与模式串进行匹配，如果模式串匹配失败，则主串移动到下一个字符，效率非常差，力扣的题目其中一个用例时4万个字符中查找，提示超时，在xocde也会执行很久
func strStrBF(haystack: String,needle: String) -> Int {
//特殊情况
if needle.count == 0 {return 0}
if (needle.count > haystack.count) {
return -1
}
for i in 0..<haystack.count - needle.count + 1 {
for j in 0..<needle.count {
let iS = haystack.index(haystack.startIndex, offsetBy: i+j)
let jS = needle.index(needle.startIndex, offsetBy: j)
//发现不相等，break
if (haystack[iS] != needle[jS]) {
break
}
//匹配成功
if j == needle.count - 1 {
return i
}
}
}
return -1
}
BM（Boyer-Moore）
BM算法根据BF算法进行优化，BF主串每次只能位移一位，而BF可以移动多位，根据是坏字符和好后缀法则
BF算法是从左往右，BM是从右往左
坏字符
从右开始匹配，如果发现匹配失败，就将主串中的这个匹配失败的字符称为坏字符，然后到模式串中查找
1.如果没有在模式串中找到，则直接将模式串右移到坏字符的后面一位
2.如果在模式串中找到：
(1)如果找到一个，则根据模式串中找到的坏字符和主串的字符对齐
(2)如果找到多个，则以最右的为准(为什么？)
3.如果要移动的位置是负数，则需要使用好后缀法则
图示：
发现坏字符f.png
查询模式串T发现没有坏字符，移动模式串到坏字符后一位，也就是g的位置.png
如果在模式串中发现坏字符fpng
模式串中找到的坏字符和主串的坏字符对齐.png
如果在模式串中找到多个坏字符的情况，则以最右为准.png
移动位数为负的情况.png
好后缀
1.如果模式串中含有好后缀，无论是中间还是头部都可以按照规则移动，如果在好后缀出现多次，则以右侧的好后缀为准;
2.如果模式串头部含有好后缀子串则可以按照规则移动，如果中间含有子串不可以;
3.如果不存在好后缀(尾部就不匹配的情况)，则以坏字符为准
4.计算时分别计算好后缀和坏字符比较两个大小，选择进行移动
图示：
好后缀cac.png
模式串完全含有好后缀✅.png
模式串头部含有好后缀子串✅.png
模式串中间含有好后缀子串❌.png
Swift代码⬇️
func strStrBM(haystack: String, needle: String) -> Int {
if needle.count == 0 {return 0}
if haystack.count == 0 {return -1}
return bm(haystack: haystack, needle: needle)
}
func bm(haystack: String, needle: String) -> Int {
var bc = Array(repeating: -1, count: 256)
badChar(needle: needle, bc: &bc)
var suffix_index = Array(repeating: -1, count: needle.count)
var prefix = Array(repeating: false, count: needle.count)
goodSuffix(needle: needle, suffix: &suffix_index, prefix: &prefix)
var i = 0
while i <= haystack.count - needle.count {
var j = needle.count - 1
while j >= 0 {
let haystackCur = haystack[haystack.index(haystack.startIndex, offsetBy: i + j)]
let needleCur = needle[needle.index(needle.startIndex, offsetBy: j)]
if haystackCur != needleCur {//找到坏字符
break
}
j -= 1
}
//模式串遍历完毕，匹配成功
if j < 0 {
return i
}
//计算坏字符需要移动的距离
let x = j - bc[Int(haystack[haystack.index(haystack.startIndex, offsetBy: i + j)].asciiValue!)]
var y = 0
if y < needle.count - 1 && needle.count - 1 - j > 0 {
//计算好后缀需要移动的距离
y = move(j: j, m: needle.count, suffix_index: suffix_index, ispre: prefix)
}
//比较大小进行移动
i = i + max(x, y)
}
return -1
}
func move(j: Int, m: Int, suffix_index: [Int], ispre: [Bool]) -> Int {
//好后缀长度
let k = m - 1 - j
//第一种情况，如果含有长度为k的好后缀，返回移动位数
if suffix_index[k] != -1 {
return j - suffix_index[k] + 1
}
//第二种情况，头部含有好后缀字串，则找头部为好后缀字串的最大长度，从长度最大的淄川开始
for r in (j+2)..<m {
//如果是头部
if ispre[m-r] == true {
return r
}
}
//第三种情况，没有发现好后缀的匹配的串，或者是头部为好后缀字串，则移动整个匹配串的长度
return m
}
//坏字符情况下的移动位数
func badChar(needle: String, bc: inout [Int]) {
for i in 0..<needle.count {
let index = needle.index(needle.startIndex, offsetBy: i)
if let ascii = needle[index].asciiValue {
bc[Int(ascii)] = i
}
}
}
//好后缀情况下的移动位数
func goodSuffix(needle: String, suffix: inout [Int], prefix: inout [Bool]) {
for i in 0..<needle.count-1 {
var j = i
var k = 0
while j >= 0 && needle[needle.index(needle.startIndex, offsetBy: j)] == needle[needle.index(needle.startIndex, offsetBy: needle.count - 1 - k)] {
j -= 1
k += 1
suffix[k] = j + 1
}
if j == -1 {
prefix[k] = true
}
}
}
KMP
找到模式串所有的最长前后缀，存入next数组，通过next数组进行移动
func strStrKMP(haystack: String, needle: String) -> Int {
if needle.count == 0 {return 0}
if haystack.count == 0 {return -1}
return kmp(haystack: haystack, needle: needle)
}
func kmp(haystack: String, needle: String) -> Int {
let next = nextList(needle: needle)
var j = 0
for i in 0..<haystack.count { //i
let iIndex = haystack.index(haystack.startIndex, offsetBy: i)
var jIndex = needle.index(needle.startIndex, offsetBy: j)
while j > 0 && haystack[iIndex] != needle[jIndex] {
j = next[j - 1] + 1
if needle.count - j + i > haystack.count {
return -1
}
jIndex = needle.index(needle.startIndex, offsetBy: j)
}
if haystack[iIndex] == needle[jIndex] {
j += 1
}
if j == needle.count {
return i - needle.count + 1
}
}
return -1
}
func nextList(needle: String) -> [Int] {
//定义next数组
var next = Array(repeating: -1, count: needle.count)
var k = -1;
for i in 1..<needle.count {
while k != -1 && needle[needle.index(needle.startIndex, offsetBy: k+1)] != needle[needle.index(needle.startIndex, offsetBy: i)] {
k = next[k]
}
if needle[needle.index(needle.startIndex, offsetBy: k+1)] == needle[needle.index(needle.startIndex, offsetBy: i)] {
k += 1
}
next[i] = k
}
return next
}
图示
计算next数组.png
