字符串匹配算法

一、概念

查找模式串在文本串中的位置的方法

模式串（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中引入坏字符预处理。预处理势必会增加空间复杂度，尤其是坏字符预处理，对于模式串长度过长的字符串可增加中间函数，排除二维数组中的空选项。