串的模式匹配
串的模式匹配也可以說子串的定位耙考，是一種重要的串運算荆忍。所謂模式匹配就是給定兩個串s1和s2既穆，在主串s1中找到子串找到一個子串等于s2的過程隐解。對于這樣的運算一般有兩種方法，一種是暴力的匹配方法升酣，而另一種則是KMP算法舷暮。
暴力的匹配方法
int BruteFroce(char s1[],char s2[])
{
int i=0,j=0;
int len1 = strlen(s1),len2=strlen(s2);
while(i<len1 && j<len2)
{
//如果當前位置匹配成功，則i和j同時移動
if(s1[i]==s2[j])
{
i++;
j++;
}
else
{
//如果不成功噩茄，則i回到匹配前的下一個位置
i = i-j+1;
//子串從頭開始匹配
j = 0;
}
}
//匹配成功放回子串在主串的位置
if(j==len2)
return i;
else //匹配失敗返回-1
return -1;
}
從這段代碼可以看得出下面，的確很暴力，逐項進行比較绩聘，對應位置的字符相等就繼續(xù)移動沥割，否則就跳出內層循環(huán)耗啦，讓j回到起點，讓i回到剛剛匹配成功的點的下一個位置驯遇，這種匹配的時間復雜度是（len1*len2）芹彬，然而有一種叫做kmp的算法比他快，時間復雜度是O（len1+len2）叉庐，之所以快的原因是減少了很多在匹配過程中不必要的回退。
kmp算法
next數(shù)組
kmp算法比起直接暴力的之所以快会喝，是因為它沒有像暴力法回退的那么
魯莽（一口氣就跑回去了）陡叠，而kmp先預處理一遍用了一個next數(shù)組
儲存當前位置前綴和后綴（除去本身）最大相等的長度。
那么next存儲了這些數(shù)字有什么用呢肢执？其實當存儲了前綴和后綴最大
相等的長度后有個很好的地方就是枉阵，如果在當前未知匹配失敗了，j是
要往回跑的预茄，但是沒有必要跑到底兴溜，可以根據(jù)next數(shù)組來判斷回到
哪里。
舉個例子
比如一個字符串為"abcaabc"
對于第0個位置來說耻陕，因為除去本身拙徽，所以前綴和后綴的最大長度為0
對于第1個位置來說，因為‘a’和‘b’不相等诗宣，所以前綴和后綴的最大長度為0
對于第2個位置來說膘怕，‘a’和‘c’不相等，‘ab’和'bc'不相等召庞，所以前綴和后綴的最大長度為0
對于第3個位置來說岛心，‘a’和'a'相等，所以前綴和后綴的最大長度為1
對于第4個位置來說篮灼，‘a’和‘a’相等忘古，所以前綴和后綴的最大長度為1
對于第5個位置來說，‘ab’和‘ab’相等诅诱，所以前綴和后綴的最大長度為2
對于第6個位置來說髓堪，‘abc’和‘abc’相等，所以前綴和后綴的最大長度為3
|位置 | 0 | 1 | 2 | 3| 4 | 5 | 6 |
|-------|:-------------------------|
|模式串 | a | b | c | a | a | b | c |
|所以前綴和后綴的最大長度為 | 0 | 0 | 0 | 1 | 1 | 2 | 3 |
而next數(shù)組只需要把上面存儲的值同一向右挪動一個單位逢艘，然后next[0]賦值為-1旦袋，這樣挪移的意思就是不包含當前位置的最大前綴和后綴的長度，所以存儲結果為：
|位置 | 0 | 1 | 2 | 3| 4 | 5 | 6 |
|-------|:-------------------------|
|模式串 | a | b | c | a | a | b | c |
|next數(shù)組 | -1 | 0 | 0 | 0 | 1 | 1 | 2 |
next數(shù)組的求法
那么next數(shù)組怎樣來求呢它改？
其實我們可以這樣來理解疤孕，假設這個next數(shù)組已經寫到了第k位，讓你來寫第k+1位央拖，那么怎么寫呢祭阀，因為第k為記錄的是前k-1個元素最大公共長度鹉戚，那么如果第k個元素等于s[next[k]+1]的話s[k+1] = next[k]+1
代碼實現(xiàn)
#define MAXSIZE 1000
int next[MAXSIZE];
void GetNext(char *s)
{
next[0] = -1;
int len = strlen(s);
int i=0,k=-1;
while(i<len)
{
//s[k]表示前綴，s[i]表示后綴
if(k==-1 || s[k]==s[i])
{
i++;
k++;
//如果相等則下一個位置next[i+1]=k+1
next[i] = k;
}
else
k = next[k];
}
}
kmp的實現(xiàn)
由圖中可以看出专控，next數(shù)組指引了當前位置不匹配時怎么走下一步抹凳，沒有必要直接讓模式串從頭開始比較
其實kmp主要是next數(shù)組那一部分的理解，如果理解了next數(shù)組和他在kmp中的工作原理伦腐，那么kmp理解就差不多了赢底。
//s1主串，s2模式串
//獲取子串的位置
int kmp(char *s1,char *s2)
{
//獲取next數(shù)組
GetNext(s2);
int i,j=0;
int len1 = strlen(s1);
int len2 = strlen(s2);
while(i<len1 && j<len2)
{
//j==-1或匹配成功則繼續(xù)下去
if(s1[i]==s2[j])
{
j++;
i++;
}
else if(j==0) //如果當前為匹配不成功柏蘑，且j=0幸冻，那么只需要i++就好
i++;
else
{
//如果j！=0且當前位置匹配不成功j回到next[j]的位置
j = next[j];
}
}
//匹配成功返回子串位置咳焚，否則返回-1
if(j==len1)
return i-j;
else
return -1;
}
//用kmp計算子串出現(xiàn)的次數(shù)
int kmp_count(char *s1,char *s2)
{
//獲取next數(shù)組
GetNext(s2);
int i,j=-1洽损，count=0;
int len1 = strlen(s1);
int len2 = strlen(s2);
while(i<len1)
{
if(a[i]==b[j])
{
i++;
j++;
}
else if(j==0)
i++;
else
j = nex[j];
if(j==len2)
{
count++;
j = nex[j]; //子串可以相互重疊
//j=0 計算不重疊子串的數(shù)量
}
}
//返回子串出現(xiàn)的次數(shù)
return count;
}
kmp練練手
學習當中參考的博客
從頭到尾徹底理解KMP
