BF、KMP算法

字元串比對算法，設定S為文本串，P為模式串。查找P是否是S的子串，即字元串比對

BF：

即暴力周遊：

i，j分别是S、P的下标，一旦不比對，j從0、i從i-j+1開始，[（i-j+1）相當于i回退到和j對應的i的下一位] 該算法複雜度在m*n上，

int BF(char *s,char *p)//查找p是否是s的子串，即 s是主串，p是模式串，
{
    int i=0,j=0;
    while(i<strlen(s)){
        if(*(p+j)=='\0')
            return i-j;
        if(*(s+i)==*(p+j)){
            ++i;
            ++j;
        }
        else{
            //i++; "aaaec","aaec" Wrong
            i=i-j+1;
            j=0;
        }
    }
    return -1;
}
           

KMP：

getNext()是用來獲得Next數組的函數，暫且不管如何獲得，

KMP的想法就是：

諸如:

s:	a b a b a b a c
p:	a b a c
           

KMP利用已經比對上的部分串的資訊，不再像BF算法那樣，通通丢掉。是以說，KMP算法的效率提升就在這裡。

示例講解：

1.現在已經比對上了前3個字元，KMP的操作就是，将p字元串向右移動2位（這是根據相同的字首和字尾的最大長度 來确定的，如何計算出來下文提到）即，i不變，j相應改變–形成p字元串右移2位，成為：

s:	a b a b a b a c
p:	    a b a c
           

這樣就比BF算法，節省了很多重複比對的時間

（比如說，如果按照BF，比對失敗之後，下一步應該是：

s:	a b a b a b a c
p:	  a b a c 
           

）

int KMP(char *s,char *p)
{
    int *next=(int *)malloc(sizeof(int)*strlen(p));
    getNext(p,next);
    //s是主串，p是模式串,通過分析已比對的字元串的字首和字尾的最大子集，比對失敗的時候來跳過某些已經完成比對的字元
    int i=0,j=0;
    while(i<strlen(s)){
        if(*(p+j)=='\0')
            return i-j;
        if(*(p+j)==*(s+i)){
            ++i;
            ++j;
        }
        else{
            if(j==0)
                i++;
            else {
                j=next[j-1];//相比BF，最主要的改變
            }
        }
    }
    return -1;
}
           

next數組：

KMP主要的思想就是：

假設現在s[i]！=p[j]，而在此之前,s[i]和p[j]是相等的，也就是一個字元串，

s: a b a b a b a c
p: a b a c
           

如上面的例子，在i=j=3之前，s、p是“aba”，是同一個字元串，此時我們讨論之前相等的這部分字元串的字首和字尾：

字首（不包含最後一個字母）：		字尾（不包含第一個字母）：
a							a
ab						       ba
           

注意：ab和ba（順序要注意） ，不是一個相同的串

是以，”aba"的字首字尾公共最大長度位1，這個的意思是

a b a
    a b a
           

将一個字元串平移之後，它的字首最多能與字尾重複的元素的個數！這樣，kmp就可以省下來 字首和字尾一樣的元素的比對時間。

如何計算next數組：

1.可以按照next數組的定義，即next[i]表示前i個元素組成的字元串的字首字尾最大公共長度

2.快速求解next數組，本身就是在字元串比對：

求aabaa的字首字尾最大公共長度

首先，第一個子串，“a”沒有字首和字尾，我在這裡把它設定位0（因為有些參考設定為-1）

後續的next數組的值，即 将字元串與自身比對

從下面這個情況開始（上面的串i=1，下面的串j=0）：

a a b a a
  a a b a a
           

如果p[i]和p[j]相等，next[i]的值就能确定了，注意是i；next[i]=next[i-1]+1;

這主要是 前i位的串的字首字尾公共長度與前i-1位的串的情況有關

如果不相等，情況多一些 :

(這裡求next數組時的這種情況可能有點問題，過幾天修改)

如果是下面這兩種，next[i]=0,然後i++，j=0

i					    i	
a b ....				a a b a a
  a b......				  a a b a a
           

但這種解決辦法并不能涵蓋所有情況，如下面這種：

i
a b a b a a
    a b a b a a 	
          j
           

這種情況就說明，上面那種解決辦法，會造成：

盡管p[i]和p[j]不比對，但不能立刻把next[i]定位0

還需要考慮p[i]是否和p[0]相比對

若比對----則應該next[i]=1

不比對應該next[i]=0

下面是next數組的求解方法：

void getNext(char *p,int *next)
{
    int i=1,j=0;//p="aaec"
    next[0]=0;
    while(i<strlen(p)){
        if(*(p+i)==*(p+j)){
            next[i]=next[i-1]+1;
            i++;
            j++;
        }
        else{
            j=0;
            if(*(p+i)!=*(p+j)){//發現不相等的i、j之後，第一步要做的是立刻把j=0，然後在比較一次
                next[i]=0;
                j=0;
                i++;
            }
            else{
                next[i]=1;
                i++;
                j++;
            }
        }
    }
    //next[0]=-1;
}
           

寫在最後 以上均為個人學習KMP算法時的想法啊，如有錯誤，請指正！

寫在最最後面

寫完kmp也能發現，kmp提高效率是對模式串p有一定的要求的，在處理不符合要求的模式串的時候，時間還不如BF，是以下一步可以仔細讨論一下不同情況下，KMP對模式串比對的效率影響。