介紹兩種字符串匹配方法
1.暴力匹配
母串用s表示，長度為m
子串用p表示，長度為n
時間復雜度為:(m-n+1)n
算法：從s串的第一個字符開始匹配，若匹配，繼續根據p向后匹配，若后續的不匹配，s右移重新匹配p?
2.KMP算法
母串用s表示，長度為m
子串用p表示，長度為n
時間復雜度為:預處理階段m
算法：①計算next[]數組 ②字符串匹配
【參考】?
?http://kb.cnblogs.com/page/176818/
?http://www.cnblogs.com/gaochundong/p/string_matching.html
?http://blog.csdn.net/v_july_v/article/details/7041827?
【C語言實現】?
?1.暴力匹配
#include <stdio.h>
#include <string.h>
int main()
{
char *s="ASDFZGasdFZGdfasdFZGsdFZGFZG";
char *p="FZG";
int i=0,j=0,count=0;
int len_s=strlen(s);
int len_p=strlen(p);
while(i<len_s&&j<len_p)
{
if (s[i]==p[j])
{
i++;
j++;
}?
else
{
i=i-j+1;
j=0;
}
if (len_p==j)
{?
printf("%d\n",i-j);//打印匹配成功的起始位置?
count++;//計算匹配次數?
j=0;
}
}
printf("%d\n",count);//打印匹配次數return 0;
}
?
?2.KMP算法?
#include <stdio.h>
#include <string.h>
int KmpSearch(char* s, char* p, int next[]);
void GetNext(char* p,int next[]);
int main()
{
char *s="asfdafASDdfda";
char *p="SD";
int next[3]={0};
GetNext(p,next);
KmpSearch(s,p,next);
return 0;
}
int KmpSearch(char* s, char* p, int next[]) ?
{ ?
int i = 0; ?
int j = 0; ?
int sLen = strlen(s); ?
int pLen = strlen(p); ?
while (i < sLen && j < pLen) ?
{ ?
//①如果j = -1，或者當前字符匹配成功（即S[i] == P[j]），都令i++，j++ ? ? ?
if (j == -1 || s[i] == p[j]) ?
{ ?
i++; ?
j++; ?
} ?
else ?
{ ?
//②如果j != -1，且當前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j] ? ? ?
//next[j]即為j所對應的next值 ? ? ? ?
j = next[j]; ?
} ?
} ?
if (j == pLen)
{
printf("%d\n",i-j);//打印匹配成功的起始位置?
return i - j; ?
}
else ?
return -1; ?
}?
void GetNext(char* p,int next[]) ?//該函數為計算next[]數組，看不太懂。。。算法暫且先記住吧
{ ?
int pLen = strlen(p); ?
next[0] = -1; ?//第一位數字置為-1，其余的是最長公共元素右移一位
int k = -1; ?
int j = 0; ?
while (j < pLen - 1) ?
{ ?
//p[k]表示前綴，p[j]表示后綴 ?
if (k == -1 || p[j] == p[k]) ??
{ ?
++k; ?
++j; ?
next[j] = k; ?
} ?
else ??
{ ?
k = next[k]; ?
} ?
} ?
}
?
