求子串

數據結構中對串的5種最小操作子集：串賦值，串比較，求串長，串連接，求子串，其他操作均可在該子集上實現

• 數據結構中串的模式匹配

KPM模式匹配演算法

 基本的模式匹配演算法

//求字串subString 在串string中的位置
function subString(string, subString){
 var i=0,j=0;
//當i或j超出範圍退出
  while(i<string.length&&j<subString.length){
   if(string[i]==subString[j]){
    ++i;++j
   }
   else{
//當匹配不成功時，i由開始位置後移一位
    i=i-j+1;j=0;
   }
 }
//如果是j超出範圍則返回i-j,如果是i超出範圍則表示未找到
 if(j>=subString.length) return i-j;
   else return false;

}

看的出來，每當匹配不成功時，i總是回朔本次匹配的開始位置
KPM，一種改進了的模式匹配演算法，解決i回朔問題

這裡引出了一個很重要的問題‘包含首碼’，

以subString='abcabcacab',為例。首碼串'abca'='abc[abca]cab'方括弧中的字串的，如果在該字串之後c處匹配失敗，只需要讓首碼串的a與括弧中的a對其，接著從匹配失敗的c處繼續匹配。

所以我們需要求出subString在j處匹配失敗後，需要向回移動j-k+1的值

假設f(j)代表subString在j之前的包含首碼中最大的k,例如'abcabca'中，k-1=1,4,即最大k為5；f(8)=5

那麼'abcabcacab'中，f(9)=f(8)+(subString[5]？==subString[8])，如果相等，則f(9)=6;如果不相等f(9)需要重新計算，因為subString[9-1]的c導致最大包含首碼不再是abca,而是一個已c結尾的包含首碼字串。實際上沒有這樣的字串;

blog.csdn.net/yukuninfoaxiom/article/details/6057736

blog.csdn.net/joylnwang/article/details/6778316/

http://www.rudy-yuan.net/archives/182/

www.webhek.com/misc/comparison-sort

• 編譯原理詞法分析器

NFA／DFA