#include <stdio.h>
#include <string.h>
#define MAXSIZE 20
typedef struct snode{
char data[MAXSIZE];
struct snode *next;
}LinkStr;
int strIndex_BF(char S[],char T[]);
int main(int argc, char *argv[])
{
char S[]="abcdabdcbdabc";
char T[]="abdc";
int result = strIndex_BF(S,T);
printf("result=%d\n",result);
return 0;
}
int strIndex_BF(char S[],char T[]){
int i=0;
int j=0;
while(i<strlen(S)&&j<strlen(T)){
if(S[i]==T[j]){
i++;
j++;
}else{
i=i-j+1;
j=0;
}
}
if(j<=strlen(T)){
return i-strlen(T);
} else{
return -1;//匹配失败
}
}
5.2.KMP算法： 5.2.1.基本概念： 1.KMP算法主要是消除了B-F算法的回溯问题，极大地提高了匹配效率； 2.基本思想：假设S为主串，T为子串，并且i和j分别表示指向S和T的元素的指针，令i和j的初始值为0，若Si=Tj，则比较下一个字符，即i和j加1；若Si!=Tj，则i不变，将j回退到next[j]的位置(下面会提到，别着急)，即j=next[j],依次类推，直到比较完成。在比较的过程中有两个规则： ①若Si=Tj,i++;j++; ②若j回退到了0的位置，此时规定next[0]=-1,此时Si+1和T0比较； 5.2.2.next[]的计算： 1 .next[]值的计算：要想使用KMP算法进行字符串匹配，按照上面的思想，首先就得算出next[]值，next[j]=k表示：当子串中的j位置的值和主串中的i位置的值不匹配时，需要将子串中的k位置的值与主串中的i位置的值比较； 2.这个K值仅和子串有关，由于回退的原因，因此k<j; 3.当子串第一个字符下标以0开始(不是以1开始)时，next[j]函数定义如下：
4.以 T="cddcdec"为例求next[j];
①j=0时，首先我们由定义知道k<j,因此k只能是-1，即next[0]=-1;
②j=1时，由定义知道k<j，因此因此k只能是0；next[1]=0;
③j=2时，k=1时，根据定义中的①式计算：SubStr(T,0,k)="c",SubStr(T,j-k,j-1)="d",由于不相等，不满足①式条件，因此满足③式：k=0;即next[2]=0;
④j=3时，k=2时，SubStr(T,0,k)="cd",SubStr(T,j-k,j-1)="dd",由于不相等，不满足①式条件，满足③式：k=0;
k=1时，SubStr(T,0,k)="c",SubStr(T,j-k,j-1)="d"，由于不相等，不满足①式条件，满足③式：k=0;结合两式，取k=0;即next[3]=0;
⑤j=4时，k=3时，SubStr(T,0,k)="cdd",SubStr(T,j-k,j-1)="ddc",由于不相等，不满足①式条件，满足③式：k=0;
k=2时，SubStr(T,0,k)="cd",SubStr(T,j-k,j-1)="dc",由于不相等，不满足①式条件，满足③式：k=0;
k=1时，SubStr(T,0,k)="c",SubStr(T,j-k,j-1)="c",此时满足定义中的①式，k=1,因此，选最大的k值，即next[4]=1;
⑥j=5时，k=4时，SubStr(T,0,k)="cddc",SubStr(T,j-k,j-1)="ddcd"，由于不相等，不满足①式条件，满足③式：k=0;
k=3时，SubStr(T,0,k)="cdd",SubStr(T,j-k,j-1)="dcd",由于不相等，不满足①式条件，满足③式：k=0;
k=2时，SubStr(T,0,k)="cd",SubStr(T,j-k,j-1)="cd"，此时满足定义中的①式，k=2;
k=1时，根据①式得，取最大值，因此不在讨论；next[5]=2;
⑦j=6时，k=5时，SubStr(T,0,k)="cddcd",SubStr(T,j-k,j-1)="ddcde",由于不相等，不满足①式条件，满足③式：k=0;
k=4时，SubStr(T,0,k)="cddc",SubStr(T,j-k,j-1)="dcde",由于不相等，不满足①式条件，满足③式：k=0;
k=3时，SubStr(T,0,k)="cdd",SubStr(T,j-k,j-1)="cde",由于不相等，不满足①式条件，满足③式：k=0;
k=2时，SubStr(T,0,k)="cd",SubStr(T,j-k,j-1)="de",由于不相等，不满足①式条件，满足③式：k=0;
k=1时，SubStr(T,0,k)="c",SubStr(T,j-k,j-1)="e",由于不相等，不满足①式条件，满足③式：k=0;因此，next[6]=0;
综上分析，next[]的数组值为：-1,0,0,0,1,2,0；
5.2.3.KMP算法匹配过程：以主串S="cddecddcdecab",子串T="cddcdec"为例，首先，我们在上面已经求出了子串T的next数组值了，因此，根据next值可以有下列步骤：
5.2.4.next函数的改进——nextval数组值 1.如子串T="aaaab"进行匹配时，next的函数值为：-1,0,,1,2,3；这种子串如果按照next[]值比较，效率低下，因此使用nextval数组值比较； 2.nextval数组值的求法：若next[j]=k,且Tj=Tk,当Si和Tj不匹配时，就不应该比较Si和Tk,而直接对Si和Tnext[k]比较。 3.以 T="cddcdec"为例求nextval[j]; ①j=0时，next[0]=-1;nextval[0]=-1; ②j=1时，next[1]=0,且T1!=T0,因此nextval[1]=next[1]=0; ③j=2时，next[2]=0,且T2!=T0,因此nextval[2]=next[2]=0; ④j=3时，next[3]=0,且T3 =T0,因此nextval[3]=next[0]=-1; ⑤j=4时，next[4]=1,且T4 =T1,因此nextval[4]=next[1]=0; ⑥j=5时，next[5]=2,且T5 !=T2,因此nextval[5]=next[5]=2; ⑦j=6时，next[6]=0,且T6 !=T0,因此nextval[6]=next[0]=-1;5.3.算法实现：//求next数组值
void get_Next(SeqStr *T,int next[]){
int j=0,k=-1;
next[0]=-1;
while(j<T->len-1){
if(k==-1||T->data[j]==T->data[k]){
j++;
k++;
next[j]=k;
}else{
k=next[k];
}
}
}
//求nextval数组织
void get_Nextval(SeqStr *T,int nextval[]){
int j=0,k=-1;
nextval[0]=-1;
while(j<T->len-1){
if(k==-1||T->data[j]==T->data[k]){
j++;
k++;
if(T->data[j]!=T->data[k]){
nextval[j]=k;
}else{
nextval[j]=nextval[k];
}
}else{
k=nextval[k];
}
}
}
//匹配
int KMP_serach(SeqStr *S,SeqStr *T){
int i=0,j=0;
int next[MAXSIZE];
get_Next(T,next);
while(i<S->len&&j<T->len){
if(S->data[i]==T->data[j]){
i++;
j++;
}else{
j=next[j];
}
}
if(j==T->len){
return i-T->len;
}else{
return -1;
}
}