一、概念
查找模式串在文本串中的位置的方法
模式串（pattern），是一个长度为m的字符串，如 'acc'
文本串（text），是一个长度为n的字符串，如'fsfffgahacjjacckkrreee'
二、变量定义
pattern:'ababaccta'
text: 'abacccababcababacctaiiiuuuuutttt'
n:pattern（模式串）长度
m:text（文本串）长度
三、算法
1、朴素算法（Naive Algorithm）
原理：即穷举法、枚举法
时间复杂度：O((n-m+1)*m) *最大计算量
2、KMP（Knuth-Morris-Pratt ）
原理：模式串预处理生成PMT，找出模式串中前n位的子串中的前缀字串与后缀子串的交集中 的最长子串长度。
预处理
| P(char) | a | b | a | b | a | c | c | t | a |
|---|---|---|---|---|---|---|---|---|---|
| M(index) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| T(value) | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 | 1 |
时间复杂度：O((n-m+1)m) - O((n-m+1)(m-1)) *后者为最大可节省的运行次数
3、BM（Boyer-Moore）
原理：利用坏字符、以及好后缀规则倒序匹配字符串的算法
坏字符：模式串中匹配到第i位与文本串中的字符不相等时，文本串中的该字符称为坏字符，通过直接检索该坏字符在模式串剩余的子串中的位置，快速移动模式串
好后缀：已经匹配的j个字符称为好后缀，通过查找该好后缀在模式串的其它位置，快速移动字符串
预处理：可以提前生成好后缀数组，减少好后缀匹配的重复工作，坏字符预处理也可减少重复工作，但会极大增加空间复杂度。
四、代码：
class StrMatch{
constructor(opts){
}
normal(pattern,text){ //正序匹配
let index = -1
let current = 0
while (index === -1 && current<text.length-pattern.length){
for(let i =0;i<pattern.length;i++){
index = current
if(text[current+i] !== pattern[i]){
current++
index = -1
break
}
}
}
return index
}
reNormal(pattern,text){ //倒序匹配
let index = -1
let current = 0
while (index === -1 && current<text.length-pattern.length){
for(let i =pattern.length-1;i>=0;i--){
index = current
if(text[current+i] !== pattern[i]){
current++
index = -1
break
}
}
}
return index
}
kpm(pattern,text){
const ptm = this.preCreantPtm(pattern)
let index = -1
let current = 0
while (index === -1 && current<text.length-pattern.length){
for(let i =0;i<pattern.length;i++){
index = current
if(text[current+i] !== pattern[i]){
current+=ptm[i]
index = -1
break
}
}
}
return index
}
bm(pattern,text){
let index = -1
let current = 0
let bg= this.preCreateBg(pattern)
let gs = this.preCreatGs(pattern)
while (index === -1 && current<text.length-pattern.length){
for(let i =pattern.length-1;i>=0;i--){
index = current
if(text[current+i] !== pattern[i]){
//current+= gs[i]
//current+= bg[i][text[current+i].charCodeAt()]
current += bg[i][text[current+i].charCodeAt()]>=gs[i]?bg[i][text[current+i].charCodeAt()]:gs[i];
index = -1
break
}
}
}
return index
}
preCreantPtm(pattern){
const ptmArr = [0]
for( let i = 1;i<pattern.length;i++){
let max = i,val=0
while(val<=0&&max>0){
for(let j = 0;j<max;j++){
val = max
if(pattern[j] !== pattern[max-j]){
val = 0
max--
break
}
}
}
ptmArr[i] = val
}
ptmArr.map((item,index)=>{
ptmArr[index] = index+1 - item
})
return ptmArr
}
preCreatGs(pattern){
//aab
const gs = []
const max = pattern.length
for(var i =0;i<max-1;i++){
let min = 1
let val = i+1
while(min<=i&&val==i+1){
for(var j =0;j<max-i;j++){
val = min
if(pattern[max-1-j] !== pattern[max-1-j-min]){
val = i+1
min++
break
}
}
}
gs[i] = val
}
gs[max-1] = 1
return gs
}
preCreateBg(pattern){
const bg = new Array(pattern.length)
for( var i =0 ;i<pattern.length;i++){
const bbg = new Array(256).fill(i+1)
for(var j=0;j<i;j++){
const code = pattern[j].charCodeAt()
bbg[code] = i-j
}
bg[i] = bbg
}
return bg
}
getMinBg(pattern,index){
}
}
const _indexOf = new StrMatch()
export default _indexOf
五、总结
字符串匹配核心就是如何快速移动模式串，通过预处理模式串可大大节省运算次数，模式串的预处理方法可多项结合运用，例如bm方法，亦可在kmp中引入坏字符预处理。预处理势必会增加空间复杂度，尤其是坏字符预处理，对于模式串长度过长的字符串可增加中间函数，排除二维数组中的空选项。
网友评论