一、概念

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

模式串（pattern），是一個(gè)長(zhǎng)度為m的字符串，如 'acc'

文本串（text），是一個(gè)長(zhǎng)度為n的字符串，如'fsfffgahacjjacckkrreee'

二、變量定義

pattern:'ababaccta'

text: 'abacccababcababacctaiiiuuuuutttt'

n:pattern（模式串）長(zhǎng)度

m:text（文本串）長(zhǎng)度

三、算法

1、樸素算法（Naive Algorithm）

原理：即窮舉法、枚舉法

時(shí)間復(fù)雜度：O((n-m+1)*m) *最大計(jì)算量

2、KMP（Knuth-Morris-Pratt ）

原理：模式串預(yù)處理生成PMT，找出模式串中前n位的子串中的前綴字串與后綴子串的交集中 的最長(zhǎng)子串長(zhǎng)度。

預(yù)處理

時(shí)間復(fù)雜度：O((n-m+1)m) - O((n-m+1)(m-1)) *后者為最大可節(jié)省的運(yùn)行次數(shù)

3、BM（Boyer-Moore）

原理：利用壞字符、以及好后綴規(guī)則倒序匹配字符串的算法

壞字符：模式串中匹配到第i位與文本串中的字符不相等時(shí)，文本串中的該字符稱為壞字符，通過(guò)直接檢索該壞字符在模式串剩余的子串中的位置，快速移動(dòng)模式串

好后綴：已經(jīng)匹配的j個(gè)字符稱為好后綴，通過(guò)查找該好后綴在模式串的其它位置，快速移動(dòng)字符串

預(yù)處理：可以提前生成好后綴數(shù)組，減少好后綴匹配的重復(fù)工作，壞字符預(yù)處理也可減少重復(fù)工作，但會(huì)極大增加空間復(fù)雜度。

四、代碼：

   
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

五、總結(jié)

字符串匹配核心就是如何快速移動(dòng)模式串，通過(guò)預(yù)處理模式串可大大節(jié)省運(yùn)算次數(shù)，模式串的預(yù)處理方法可多項(xiàng)結(jié)合運(yùn)用，例如bm方法，亦可在kmp中引入壞字符預(yù)處理。預(yù)處理勢(shì)必會(huì)增加空間復(fù)雜度，尤其是壞字符預(yù)處理，對(duì)于模式串長(zhǎng)度過(guò)長(zhǎng)的字符串可增加中間函數(shù)，排除二維數(shù)組中的空選項(xiàng)。