串的模式匹配(6)

scanf(\

if((fp=fopen(filename,\以读的方式打开文件 { printf(\文件打开失败，按请按任意键退出！\\n\ getch(); exit(0);

}

printf(\请输入要检索的单词：\ scanf(\ T.length=strlen(T.ch); l=0;//行计数器清0 while(!feof(fp)){ fgets(S.ch,MAXSTRLEN,fp);

S.length=lenth(S.ch);//求读入的串的长度 if(feof(fp)) break; l++;//行计数器自增1 k=1;//初始化开始检索位置 i=0;//初始化行单词计数器

while(k

sz[i]=j;//记录匹配单词位置

24

} }

}

}

k=j+T.length;//继续寻下一个子串的检索

if(i>0) { }

printf(\行号：%d,次数：%d,位置分别为：\for(m=1;m<=i;m++) printf(\printf(\

⑶ 在串的链式存储下，利用串的模式匹配KMP算法实现上述功能部分代码如下：

//初始化链表，存储出现的次数和行号 Status IninLinkList(LinkList &L) {

LinkList p,q;

L=(LinkList)malloc(sizeof(Lnode));//头结点

p=(LinkList)malloc(sizeof(Lnode));//第一个节点存储出现次数 q=(LinkList)malloc(sizeof(Lnode));//第二个结点存储第一个行号 if(!L) return(0); L->next=p; L=p; p->next=q; L->data=0; q->data=0; q->next=NULL;

25

return(1); }

//更新链表的第一个结点

Status ListInsertfreq(LinkList &L) {

L->data=L->data+1; return(L->data); }

//更新链表的第二个及其后的结点

Status LinsInsertline(LinkList &L,int line) {

LinkList p,first; first=L;

while(first->next)

first=first->next;

if(line==1) first->data=1;//修改第一个行号结点的值 else if(line!=first->data) { //生成后边几个点

p=(LinkList)malloc(sizeof(Lnode)); first->next=p; p->data=line; p->next=NULL; return(OK);

}

26

else if(line==first->data) return(1); return(1); }

//打印行号

Status printlines(LinkList &head) {

head=head->next; while(head) { if(head->data!=0) printf(\ //将默认行号初始化为0 head=head->next;

}

return(1); }

//求串searchwords的next函数值并存入数组kmp Status getnext(char *searchwords,int *kmp) {

int i=0; int j=-1; int max=0;

max=strlen(searchwords); while(i

if(j==-1||searchwords[i]==searchwords[j])

27

}

{ }

else j=kmp[j];

++i;++j; kmp[i]=j;

return(1); }

//KMP匹配函数，利用模式串searchwords的getnext函数求searchwords在主串buff中的位置

Status Index(char *buff,char *searchwords,LinkList &L,int line,int *kmp) {

int i=0,j=0,k=0; int blength=0,search=0;

blength=strlen(buff);//求主串串长 search=strlen(searchwords);//求模式串串长 while(j<=(search-1)) {

if(j==-1||buff[i]==searchwords[j]) { }

else j=kmp[j];

if(j>search-1)//找出所有关键字的出现次数 {

j=0;

28

++i;++j;