|
KMP算法中最重要的就是next[i]数值 next[0]=-1是固定的 其他next[i]的确立依据前0-(i-1)字符首尾最大子字符串长度 从百度百科上截了张图，就以这个进行分析 http://baike.baidu.com/view/659777.htm  前面字符串是 abcd 不存在，next[4]=0; 如i=5 前面字符串是 abcda 存在a ，next[5]=1; 如i=8 前面字符串是 abcdaabc 存在abc，next[8]=3; 优化说明 如p[4]=a,对应next[4]=0,但p[0]也是a,优化后next[4]=next[0]=-1; 如p[5]=a,对应next[4]=1,但p[1]是b,不处理; 查找最大子字符串说明 基本 见函数chushi() 从最大子字符串开始匹配直到有结果，或不存在 如i=7，就是从abcdaab中查找最大子字符串 第一次 abcdaa bcdaab 不一致 第二次 abcda cdaab 不一致 第三次 abcd daab 不一致 第四次 abc aab 不一致 第五次 ab ab 一致 返回结果2 到最后都不匹配时返回0 优化 基于前一次的结果进行判断，只要判断一个字符就可以 见函数chushi2() 当i=8时，对于前一次(i-1=7)匹配的长度是2(ab),只需比较p[7]和p[2]是否相等，一致则长度加1，为3(abc) 当i=6时，前一次匹配长度是1，但p[5]和p[1]不等， 接下来比较p[5]和p[0],一致结果为1，否则为0; 注:next[0]=-1,next[1]=0是事先确立好的，通过这种方式只能先获取未优化过的 #include <stdio.h> #include <stdlib.h> #include <string.h> int *next=NULL; char* scr=NULL; int len=0; void setnext(int i)//确定next[i]的值 { int j; for(j=1;j<i;j++)//找出首尾最大子字符串长度(查找范围:字符下标 0 - (i-1)) { if(strncmp(scr,scr+j,i-j)==0) { next[i]=i-j; //优化，去掉也正常运行 if (scr[i]==scr[next[i]]) { next[i]=next[next[i]]; } //优化完毕 return; } } next[i]=0;//没找到就是0 } void shownext()//输出特征向量 { int pos; for (pos=0;pos<len;pos++) { printf("%d ",next[pos]); } printf("\n"); } void chushi() { int len=strlen(scr); int pos; next[0]=-1; for(pos=1;pos<len;pos++) { setnext(pos); } } void youhua()//优化作用 { int len=strlen(scr); int pos; for (pos=1;pos<len;pos++) { if (scr[pos]==scr[next[pos]]) { next[pos]=next[next[pos]]; } } } void chushi2()//这个查找子字符串更快些，时间复杂度为n { int len=strlen(scr); int pos; next[0]=-1; next[1]=0; for (pos=2;pos<len;pos++) { if (scr[pos-1]==scr[next[pos-1]]) { next[pos]=next[pos-1]+1; } else { if (scr[pos-1]==scr[0]) { next[pos]=1; } else next[pos]=0; } } youhua();//优化处理 } int pipei(char ch,int i)//将字符ch与scr第i位进行匹配，返回下一次匹配位置 { if (ch==scr[i]) { return i+1; } else { if (next[i]==-1) { return 0; } else return pipei(ch,next[i]); } } void mysearch(char* str,int num)// { int strlens=strlen(str); int pos; int i=0; for (pos=0;pos<strlens;pos++) { i=pipei(str[pos],i); if (i==len) { printf("发现字符串 第%d行 位置%d!\n",num,pos-len+1); i=0; } } } void readtxt()//读取文件匹配字符串 { FILE*fp=fopen("test.txt","r");//打开文件"test.txt" char buff[1024]; int num=0; if (fp==NULL) { printf("打开失败!\n"); return; } while(fgets(buff,1024,fp))//一行行进行查找 { num++; mysearch(buff,num); } } int main() { scr=malloc(20); printf("输入要查找的字符串:"); scanf(" %s",scr); // strcpy(scr,"abcdaabcab"); // 演示 // 可看http://baike.baidu.com/view/659777.htm // len=strlen(scr); next=malloc(sizeof(int)*len); printf("输入字符串为:%s 长度为:%d\n",scr,len); //两种初始方式随便选一个，第二个好些 chushi(); // chushi2(); printf("初始化完毕\n"); shownext();//显示KMP特征向量 //////////////// readtxt();//在文件中查找字符串， if (scr!=NULL) free(scr); if (next!=NULL) free(next); return 0; } |
|
|
