求子串位置的定位函數(shù)index
子串的定位操作通常稱作串的模式匹配，是各種串處理系統(tǒng)中最重要的操作之一。
一個(gè)最簡(jiǎn)單的匹配方法是：
從左到右一個(gè)個(gè)匹配，如果這個(gè)過(guò)程中有某個(gè)字符不匹配，就跳回去，將模式串向右移動(dòng)一位。
初始化：
之后我們只需要比較i指針指向的字符和j指針指向的字符是否一致。如果一致就都向后移動(dòng)，如果不一致，如下圖：
A和E不相等，那就把i指針移回第1位（假設(shè)下標(biāo)從0開始），j移動(dòng)到模式串的第0位，然后又重新開始這個(gè)步驟：
算法實(shí)現(xiàn)如下：
int indexSubStr(MyString *S,MyString *substr,int pos){
int i = pos,j = 0;
while(i < S->length && j < substr->length){
if(*(S->str + i) == *(substr->str + j)){
i++;
j++;
}else{
i = i - j + 1;
j = 0;
}
}
if(j == substr->length){
return i - j;
}else{
return -1;
}
}
上述算法的匹配過(guò)程易于理解，且在某些應(yīng)用場(chǎng)合，如文本編輯等，效率也較高。較好的情況下，此算法的時(shí)間復(fù)雜度為O(n+m)。然而在有些情況下，該算法的效率卻很低。例如，當(dāng)模式串為“00000001”，而主串為“00000000000000000000000000000001”時(shí)，每趟比較都在模式的最后一個(gè)字符出現(xiàn)不等，此時(shí)需要將指針i重新回溯到i-6的位置上，并從模式的第一個(gè)字符開始重新比較，則最壞的情況下的時(shí)間復(fù)雜度為O(n*m)。
模式匹配的一種改進(jìn)算法——KMP算法
這種改進(jìn)算法是D.E.Knuth與V.R.Pratt和J.H.Morris同時(shí)發(fā)現(xiàn)的，因此人們稱它為KMP算法。此算法可以在O(n+m)的時(shí)間數(shù)量級(jí)上完成串的模式匹配操作。
其改進(jìn)在于：每一趟匹配過(guò)程中出現(xiàn)字符比較不等時(shí)，不需回溯i指針，而是利用已經(jīng)得到的部分匹配的結(jié)果，將模式串向右滑動(dòng)盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。
如：
此時(shí)，移動(dòng)j到一個(gè)合適的位置k繼續(xù)比較：
如下圖也是一樣的情況：
此時(shí)，移動(dòng)j到一個(gè)合適的位置k繼續(xù)比較：
至此我們可以大概看出一點(diǎn)端倪，當(dāng)匹配失敗時(shí)，j要移動(dòng)的下一個(gè)位置k。存在著這樣的性質(zhì)：最前面的k個(gè)字符和j之前的最后k個(gè)字符是一樣的。如下圖所示：
下面討論一般情況。假設(shè)主串為“s1s2....sn”,模式串為“p1p2...pm”,從上例的分析可知，為了實(shí)現(xiàn)改進(jìn)算法，需要解決下述問(wèn)題：當(dāng)匹配過(guò)程中產(chǎn)生“失配”（即si≠pj）時(shí)，模式串“向右滑動(dòng)”可行的距離多遠(yuǎn)，換句話說(shuō)，當(dāng)主串中第i個(gè)字符與模式中第j個(gè)字符“失配”時(shí)，主串中第i個(gè)字符（i指針不回溯）應(yīng)與模式串中哪個(gè)字符再比較？
假設(shè)此時(shí)應(yīng)與模式中第k（k<j）個(gè)字符繼續(xù)比較，則模式中前k-1個(gè)字符的子串必須滿足下列關(guān)系式，且不可能存在k’>k滿足下列關(guān)系式：
“p1 p2 ... pk-1” = “si-k+1 si-k+2 ... si-1”
即下圖藍(lán)框圈起的上下兩部分：
而已經(jīng)得到的部分匹配的結(jié)果是：
“pj-k+1 pj-k+2 ... pj-1” = “si-k+1 si-k+2 ... si-1”
即下圖藍(lán)框圈起的上下兩部分：
那么可以推得下列等式：
“p1 p2 ... pk-1” = “pj-k+1 pj-k+2 ... pj-1” 。
即下圖表示的兩邊相等的部分：
即，若模式中存在滿足上式的兩個(gè)子串，則當(dāng)匹配過(guò)程中，主串中第i個(gè)字符與模式中第j個(gè)字符比較不等時(shí)，僅需將模式串向右滑動(dòng)至模式中第k個(gè)字符和主串中第i個(gè)字符對(duì)齊，此時(shí)，模式中前k-1個(gè)字符的子串“p1 p2 ... pk-1”必定與主串中第i個(gè)字符之前長(zhǎng)度為k-1的子串“si-k+1 si-k+2 ... si-1”相等，由此，匹配僅需從模式中第k個(gè)字符與主串中第i個(gè)字符比較起繼續(xù)進(jìn)行。
因?yàn)樵趐的每一個(gè)位置都可能發(fā)生不匹配，也就是說(shuō)我們要計(jì)算每一個(gè)位置j對(duì)應(yīng)的k，所以用一個(gè)數(shù)組next來(lái)保存，next[j] = k，表示當(dāng)s[i] != p[j]時(shí)，j指針的下一個(gè)位置。由此可引出模式串的next函數(shù)的定義：
| next[j]= | -1 | 當(dāng)j = 0時(shí) |
|---|---|---|
| Max{k|0<k<j且“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”} | 當(dāng)此集合不空時(shí) | |
| 0 | 其他情況 |
求得模式串的next函數(shù)之后，匹配可如下進(jìn)行：
假設(shè)以指針i和j分別指示主串和模式中正待比較的字符，令i的初值為pos，j的初值為0。
若在匹配的過(guò)程中s[i]=p[j]，則i，j分別增1，繼續(xù)比較；
若s[i]≠p[j]，則i不變，而j退到next[j]的位置再比較，若相等，則指針各自增1，否則j再退到next[j]的位置再比較，以此類推；
若j退到值為0，則此時(shí)需將模式串繼續(xù)向右滑動(dòng)一個(gè)位置，即從主串的下一個(gè)字符si+1起和模式串重新開始匹配。
KMP算法實(shí)現(xiàn)如下：
int myStringIndexSubString(MyString *S,MyString *substr,int pos){ //KMP算法
int i = pos,j = 0;
if(!S || !substr || pos > S->length) return -1;
int *nextval = getKMPNext(substr);
if(!nextval) return -1;
while(i < S->length && j < substr->length){
if(*(S->str + i) == *(substr->str + j)){
i++;
j++;
}else{
j = *(nextval+j); //i不需要回溯，j回到指定位置
if(j == -1){
i++; //當(dāng)j為-1時(shí)，要移動(dòng)的是i
j++; //j歸0
}
}
}
free(nextval);
if(j == substr->length){
return i - j;
}else{
return -1;
}
}
KMP的算法是在已知模式串的next函數(shù)值的基礎(chǔ)上執(zhí)行的，那么，如何求得模式串的next函數(shù)值是很重要的。
從上述討論可見，此函數(shù)值僅取決于模式串本身而和相匹配的主串無(wú)關(guān)。我們可以從分析其定義出發(fā)用遞推的方法求得next函數(shù)值。
先來(lái)看第一個(gè)：當(dāng)j為0時(shí)，如果這時(shí)候不匹配，怎么辦？
像上圖這種情況，j已經(jīng)在最左邊了，不可能再移動(dòng)了，這時(shí)候要應(yīng)該是i指針后移。所以在代碼中才會(huì)有next[0] = -1這個(gè)初始化。如果是當(dāng)j為1的時(shí)候呢？
顯然，j指針一定是后移到0位置的。因?yàn)樗懊嬉簿椭挥羞@一個(gè)位置了，next[1] =0。
當(dāng){0<k<j且“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”}集合不空時(shí)，設(shè)next[j] = k,這表明在模式串中存在下列關(guān)系：
“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”，其中k為滿足0<k<j的某個(gè)值，并且不可能存在k'>k滿足前面的等式。
此時(shí)next[j+1] =？可能有兩種情況：
1.p[k] = p[j],如下圖所示：
前面next[j] = k時(shí)，已經(jīng)存在“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”這一等式，若p[k] = p[j]，則很容易的得出：
“p0 p1 ... pk” = “pj-k pj-k+1 ... pj”，
即在此基礎(chǔ)上兩邊加上相等的p[k]、 p[j]，
則next[j+1] = k+1，即next[j+1]=next[j] +1。
2.p[k] != p[j]，如下圖所示：
此時(shí)“p0 p1 ... pk” != “pj-k pj-k+1 ... pj”，可以把求next函數(shù)值的問(wèn)題看成是一個(gè)模式匹配的問(wèn)題，整個(gè)模式串既是主串又是模式串，而當(dāng)前在匹配過(guò)程中，已有“p0 p1 ... pk-1” = “pj-k pj-k+1 ... pj-1”這一等式，則當(dāng)p[k] != p[j]時(shí)應(yīng)將模式串向右滑動(dòng)至以模式串中的第next[k]個(gè)字符和主串中的第j個(gè)字符相比較，如下圖所示：
這就是為什么代碼中為k = *(nextval+k)
當(dāng)其他情況時(shí)，next[j] =0，這表明模式串從頭開始比較。
getKMPNext函數(shù)
static int *getKMPNext(MyString *substr){
int *nextval = (int *)malloc((substr->length)*sizeof(int));
int j=0,k=-1;
if(nextval){
*nextval = -1;
while(j<substr->length){
if(k == -1 || *(substr->str+j) == *(substr->str+k)){
if(*(substr->str+(++j)) == *(substr->str+(++k))){ //兩個(gè)字符相等時(shí)跳過(guò)
*(nextval+j) = *(nextval+k);
}else{
*(nextval+j) = k;
}
}else{
k = *(nextval+k);
}
}
return nextval;
}else{
return NULL;
}
}
在上面的getKMPNext函數(shù)中還修正了next的值。前面定義的Next表達(dá)式有一個(gè)小缺陷，看一個(gè)例子：
顯然，根據(jù)Next表達(dá)式得到的next數(shù)組應(yīng)該是[ -1，0，0，1 ]，所以下一步我們應(yīng)該是把j移動(dòng)到第1個(gè)元素：
不難發(fā)現(xiàn)，這一步是完全沒(méi)有意義的。因?yàn)楹竺娴腂已經(jīng)不匹配了，那前面的B也一定是不匹配的，同樣的情況其實(shí)還發(fā)生在第2個(gè)元素A上。
發(fā)生問(wèn)題的原因在于P[j] == P[next[j]]。
所以在getKMPNext函數(shù)中添加一個(gè)判斷條件：
if(*(substr->str+(++j)) == *(substr->str+(++k))){ //兩個(gè)字符相等時(shí)跳過(guò)
修正后的next數(shù)組是[ -1，0，0，0 ]。
getKMPNext函數(shù)的時(shí)間復(fù)雜度為O(m)。通常，模式串的長(zhǎng)度m比主串的長(zhǎng)度n要小的多，因此，對(duì)整個(gè)匹配算法來(lái)說(shuō)，所增加的這點(diǎn)時(shí)間是值得的。
最前面介紹的匹配算法的時(shí)間復(fù)雜度是O(n*m),但在一般情況下，其實(shí)際的執(zhí)行時(shí)間近似于O(n+m),因此至今仍被采用。KMP算法僅當(dāng)模式串與主串之間存在許多“部分匹配”的情況下才顯得比這個(gè)算法快得多。但是KMP算法的最大特點(diǎn)是指示主串的指針不需要回溯，整個(gè)匹配過(guò)程中，對(duì)主串僅需從頭至尾掃描一遍，這對(duì)處理從外設(shè)輸入的龐大文件很有效，可以邊讀入邊匹配，而無(wú)需回頭重讀。
KMP算法的實(shí)現(xiàn)基于之前的C封裝字符串、字符串?dāng)?shù)組對(duì)象內(nèi)容：C封裝字符串、字符串?dāng)?shù)組對(duì)象
testMyString.c文件：
#include <stdio.h>
#include <malloc.h>
#include "MyString.h"
int printMyString(MyString *str){
printf("%s, ",str->str);
printf("length :%d\n",str->length);
return 0;
}
int printMyStringElem(MyString **str){
printf("%s ",(*str)->str);
return 0;
}
int main(void){
int i;
char words[] = {"without new experiences, something inside of us sleeps."};
MyString *str_a = NULL;
MyString *str_b = NULL;
MyString *str_c = NULL;
MyStringArray *str_array = NULL;
str_a = myStringAssign("hello ");
str_c = myStringAssign("hello ");
printf("str_a :");
printMyString(str_a);
printf("is MyString empty: %d\n",isMyStringEmpty(str_a));
if(compareMyString(str_a,str_c)==0){
printf("str_a equals str_c\n");
}else{
printf("str_a is not equal str_c\n");
}
clearMyString(str_a);
printf("is MyString empty: %d\n",isMyStringEmpty(str_a));
if(compareMyString(str_a,str_c)==0){
printf("str_a equals str_c\n");
}else{
printf("str_a is not equal str_c\n");
}
destroyMyString(str_a);
str_a = copyMyString(str_c);
str_b = myStringAssign("Mr Bluyee");
printf("str_b :");
printMyString(str_b);
destroyMyString(str_c);
str_c = concatMyString(str_a,str_b);
printf("str_c :");
printMyString(str_c);
printf("the MyString : Mr Bluyee index: ");
i = myStringIndexSubString(str_c,str_b,0);
printf("%d\n", i);
printf("the char \'B\' index: %d\n", myStringIndexChar(str_c,'B',0));
insertMyString(str_a,str_b,str_a->length);
printf("str_a :");
printMyString(str_a);
destroyMyString(str_c);
str_c = substrMyString(str_a,0,5);
printf("str_c :");
printMyString(str_c);
destroyMyString(str_c);
str_c = myStringAssign(words);
str_array = splitMyString(str_c,' ');
str_array->traverse(str_array,printMyStringElem);
destroyMyString(str_a);
destroyMyString(str_b);
destroyMyString(str_c);
DestroyMyStringArray(str_array);
return 0;
}
KMP匹配的調(diào)用的代碼段是：
printf("the MyString : Mr Bluyee index: ");
i = myStringIndexSubString(str_c,str_b,0);
printf("%d\n", i);
編譯：
gcc MyString.c MyString.h MyStringArray.c MyStringArray.h testMyString.c -o testMyString
運(yùn)行testMyString：
str_a :hello , length :6
is MyString empty: 0
str_a equals str_c
is MyString empty: 1
str_a is not equal str_c
str_b :Mr Bluyee, length :9
str_c :hello Mr Bluyee, length :15
the MyString : Mr Bluyee index: 6
the char 'B' index: 9
str_a :hello Mr Bluyee, length :15
str_c :hello, length :5
without new experiences, something inside of us sleeps.
本篇文章部分內(nèi)容整理自：（原創(chuàng)）詳解KMP算法
