#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;
}