|
KMP算法中最重要的就是next[i]數(shù)值 next[0]=-1是固定的 其他next[i]的確立依據(jù)前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; 優(yōu)化說明 如p[4]=a,對應(yīng)next[4]=0,但p[0]也是a,優(yōu)化后next[4]=next[0]=-1; 如p[5]=a,對應(yīng)next[4]=1,但p[1]是b,不處理; 查找最大子字符串說明 基本 見函數(shù)chushi() 從最大子字符串開始匹配直到有結(jié)果，或不存在 如i=7，就是從abcdaab中查找最大子字符串 第一次 abcdaa bcdaab 不一致 第二次 abcda cdaab 不一致 第三次 abcd daab 不一致 第四次 abc aab 不一致 第五次 ab ab 一致 返回結(jié)果2 到最后都不匹配時返回0 優(yōu)化 基于前一次的結(jié)果進行判斷，只要判斷一個字符就可以 見函數(shù)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],一致結(jié)果為1，否則為0; 注:next[0]=-1,next[1]=0是事先確立好的，通過這種方式只能先獲取未優(yōu)化過的 #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; //優(yōu)化，去掉也正常運行 if (scr[i]==scr[next[i]]) { next[i]=next[next[i]]; } //優(yōu)化完畢 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()//優(yōu)化作用 { 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()//這個查找子字符串更快些，時間復(fù)雜度為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();//優(yōu)化處理 } 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("發(fā)現(xiàn)字符串 第%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; } |
|
|
