1. BF算法
英文全称：Brute Force，也即暴力匹配算法。主要思路是：遍历主串，逐个子串与模式串进行比较。代码如下（kotlin编写）：
/**
* 暴力匹配算法
*
* @param main 主串
* @param pattern 模式串
*/
fun stringMatchBF(main: String, pattern: String): Int {
var n = main.length
var m = pattern.length
if (n < m)
return -1
if (n == m) {
if (main == pattern)
return 0
return -1
}
//遍历匹配
var flag: Boolean
for (i in 0..n - m) {
flag = true
for (j in pattern.indices) {
if (main[i + j] != pattern[j]) {
flag = false
break
}
}
if (flag) return i
}
return -1
}
时间复杂度：O(n*m)，其中 n 为主串长度，m 为模式串长度
2. RK算法
根据两位发明者 Rabin 和 Karp 的名字来命名。与 BF 算法其实类似，BF 算法在比较子串与模式串的时候，是遍历比较的，而如果我们算出子串的 hash 值，最后只需要比较子串与模式串的 hash 值是否一致，如果相等则说明找到了，与遍历相比只需要一个 hash 值比较判断就可完成。
这里的关键是 hash 算法，要非常高效，这样其性能才能好过 BF 算法。
/**
* RK算法。为了方便，这里假设字符串只包含英文字符 [a-z]
* 实际上字符串是任意的，这时我们需要找到一个高效的 hash 算法，并且 hash 冲突相对比较少
*
* @param main 主串
* @param pattern 模式串
*/
fun stringMatchRK(main: String, pattern: String): Int {
var n = main.length
var m = pattern.length
if (n < m)
return -1
if (n == m) {
if (main == pattern)
return 0
return -1
}
//模式串的 hash 值
var patternHash = 0
//我们将字符 a-z 分别对应 0-25，每位分别相加
for (ch in pattern) {
patternHash += ch - 'a'
}
//遍历匹配
var subStrHash = -1
for (i in 0..n - m) {
if (subStrHash == -1) {
subStrHash = 0
//计算第一个子串的 hash 值
for (j in 0 until m) {
subStrHash += (main[j] - 'a')
}
} else {
//主串的相邻2个子串，只是头尾字符不一样，这样计算非常节省时间
subStrHash = subStrHash - (main[i - 1] - 'a') + (main[i + m - 1] - 'a')
}
if (subStrHash == patternHash) {
//这里需要注意，如果产生 hash 冲突，实际上还需要将子串与模式串逐一匹配
return i
}
}
return -1
}
3. BM算法
fun findSubStr(mainString: String, patternString: String?): Int {
if (patternString.isNullOrEmpty()) {
return -1
}
if (mainString.length < patternString.length)
return -1
val n = mainString.length
val m = patternString.length
//构造坏字符hash表，模式串中的每个字符，在模式串中的位置。数组下标对应 ASCII 码值，初始值都为 -1
//现在只考虑字符集比较少的情况，如果字符串字符集比较大的情况，则不是很适用
val badCharHashTable = IntArray(256) { -1 }
//数组下标对应的是好后缀子串 {u} 的长度，对应的值是模式串中与 {u} 相匹配的子串 {u*} 的起始下标值，初始值都为 -1
val suffix = IntArray(m) { -1 }
//用来记录模式串的后缀子串是否能够匹配模式串的前缀子串，数组下标对应的是后缀子串 {u} 的长度
val prefix = BooleanArray(m) { false }
for (i in patternString.indices) {
badCharHashTable[patternString[i].toInt()] = i
}
//计算 suffix、 prefix 数组的值，逐步将模式串的子串 [0, i] 与模式串进行比较，求得公共后缀子串，i 取值范围[0, m - 1]
for (i in 0 until m - 1) {
var j = i
var k = 0 //公共后缀子串的长度
//计算公共后缀子串
while (j >= 0 && patternString[j] == mainString[m - k - 1]) {
j--
k++
suffix[k] = j + 1
}
//此时说明该子串既是前缀子串也是后缀子串
if (j == -1) {
prefix[k] = true
}
}
var i = 0
//从主串的位置 0 开始匹配，从左往右开始匹配，最多到位置 n-m 处结束
while (i <= n - m) {
//从后往前逐一匹配
var j = m - 1
while (j >= 0) {
if (mainString[i + j] != patternString[j]) {
//找到坏字符，j 就是主串中坏字符在模式串中对应的位置
break
}
j--
}
//说明整个字符串都匹配成功了，直接找到模式串了
if (j < 0) {
return i
}
//计算模式串匹配往后挪动的距离，坏字符在主串中的位置是 i + j
//需要找到主串中，是否还有另一个可匹配的字符，没有则为 -1
var step1 = j - badCharHashTable[mainString[i + j].toInt()]
//如果有好后缀，则可计算通过好后缀可移动多少步
var step2 = 0
if (j < m - 1) {
//好后缀长度
val goodSuffixLength = m - j - 1
//说明该好后缀在模式串中能够匹配到其他子串
if (suffix[goodSuffixLength] != -1) {
step2 = j - suffix[goodSuffixLength] + 1
} else {
//好后缀的后缀子串起始位置从 j + 2 开始
var r = j + 2
while (r <= m -1) {
if (prefix[m - r]) {
step2 = r
break
}
r++
}
}
if (step2 == 0)
step2 = m
}
i += max(step1, step2)
}
return -1
}
4. KMP算法
fun kmp(mainString: String, patternString: String): Int {
if (patternString.isNullOrEmpty()) {
return -1
}
if (mainString.length < patternString.length)
return -1
val m = patternString.length
var next = getNext(patternString)
var j = 0
for (i in mainString.indices) {
while (j > 0 && mainString[i] != patternString[j]) {
j = next[j - 1] + 1
}
if (mainString[i] == patternString[j]) {
j++
}
if (j == m) { //找到模式串了
return i - m + 1
}
}
return -1
}
//计算 next 数组
fun getNext(str: String): Array<Int> {
var m = str.length
var next = Array(str.length) { -1 }
next[0] = -1
var k = -1
for (i in 1 until m) {
while (k != -1 && str[k + 1] != str[i]) {
k = next[k]
}
if (str[k + 1] == str[i]) {
k++
}
next[i] = k
}
return next
}
5. AC自动机
private class AcNode(var data: Char) {
var children = TreeMap<Char, AcNode>()
var isEndChar = false
var length = -1
var fail: AcNode? = null
}
class AcTree() {
class MatchInfo(val position: Int, val length: Int)
private val root: AcNode = AcNode('/')
//构建trie树
fun insert(str: String?) {
if (str.isNullOrEmpty())
return
var p = root
for (i in str.indices) {
var childNode = p.children[str[i]]
if (childNode == null) {
childNode = AcNode(str[i])
p.children[str[i]] = childNode
}
p = childNode
}
p.isEndChar = true
p.length = str.length
}
//构建失败指针
fun buildFailPointer() {
var queue: Queue<AcNode> = LinkedList()
root.fail = null
queue.add(root)
while (queue.isNotEmpty()) {
var p = queue.remove()
for (pc in p.children.values) {
if (pc == null)
continue
if (p == root) {
pc.fail = root
} else {
var q = p.fail
while (q != null) {
var qc = q.children[pc.data]
if (qc != null) {
pc.fail = qc
break
}
q = q.fail
}
if (q == null) {
pc.fail = root
}
}
queue.add(pc)
}
}
}
//多模式传匹配
fun match(str: String?): List<MatchInfo>? {
if (str.isNullOrEmpty())
return null
val list = mutableListOf<MatchInfo>()
var p: AcNode? = root
for (i in str.indices) {
while (p!!.children[str[i]] == null && p != root) {
p = p.fail
}
p = p.children[str[i]]
if (p == null) {
p = root
}
var tmp = p
while (tmp != root) {
if (tmp!!.isEndChar) {
var pos = i - tmp!!.length + 1
list.add(MatchInfo(pos, tmp.length))
}
tmp = tmp.fail
}
}
return list
}
}
网友评论