KMP算法中最重要的就是next[i]數(shù)值
next[0]=-1是固定的
其他next[i]的確立依據(jù)前0-(i-1)字符
首尾最大子字符串長度 從百度百科上截了張圖，就以這個(gè)進(jìn)行分析
http://baike.baidu.com/view/659777.htm 如i=4
前面字符串是 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
到最后都不匹配時(shí)返回0
優(yōu)化基于前一次的結(jié)果進(jìn)行判斷，只要判斷一個(gè)字符就可以
見函數(shù)chushi2()
當(dāng)i=8時(shí)，對于前一次(i-1=7)匹配的長度是2(ab),只需比較p[7]和p[2]是否相等，一致則長度加1，為3(abc)
當(dāng)i=6時(shí)，前一次匹配長度是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++)//找出首尾最大子字符串長度(查找范圍:字符下標(biāo) 0 - (i-1))
{
if(strncmp(scr,scr+j,i-j)==0)
{
next[i]=i-j;
//優(yōu)化，去掉也正常運(yùn)行
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()//這個(gè)查找子字符串更快些，時(shí)間復(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位進(jìn)行匹配，返回下一次匹配位置
{
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))//一行行進(jìn)行查找
{
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);
//兩種初始方式隨便選一個(gè)，第二個(gè)好些 chushi();
// chushi2();
printf("初始化完畢\n");
shownext();//顯示KMP特征向量
////////////////
readtxt();//在文件中查找字符串，
if (scr!=NULL)
free(scr);
if (next!=NULL)
free(next);
return 0;
}
