文档助手算法以及算法分析.rar_KMP算法_算法

程序流程：打开用户指定文件－＞把整个文件当作一个字符串保存到数组－＞由用户输入需查找的子串，并保存 到栈中，并初始化栈－＞计算每个子串的next函数值，保存到各自的next数组里－＞调用kmp模式匹配函数－＞打 印出结果 算法思想：用栈结构保存输入的几个字符串，在结构体里为每个串设置几个属性，分别为串本身，长度，出现的 次数，串的next数组值，以及与主串匹配的j值。用栈的主要目的是为了在实现多个子串同时比较时模式匹配算法 的地实现。主体部分，即模式匹配的算法思想,结合代码,分析如下: void Index_KMP(char S[],int n,Stack T,int pos) { int Slength=n;//主串长度 int i =pos ;//起始匹配位置 T.temp=T.base; while( i <Slength){ T.temp=T.base; while(T.temp!=T.top) {if((*T.temp).j != 0 &&S[i-1] !=(*T.temp).ch[(*T.temp).j-1]) { (*T.temp).j = (*T.temp).next[(*T.temp).j-1]; } T.temp++; }//这个while循环,temp指针指向当前子串.当每个子串不与主串匹配时,计算出每个的next值 T.temp=T.base; int count=0;//这个变量用于保存已经满足条件的子串数目. while(T.temp!=T.top) { if((*T.temp).j==0||S[i-1]==(*T.temp).ch[(*T.temp).j-1]) {count++;} T.temp++; }//这个循环用于计算满足匹配条件的子串数目,保存到count变量里. //下面这个if语句是当全部子串都满足匹配条件时(tcount变量是指输入子串的数目,当count==tcount时,表明全部子串 都已经符合匹配的条件),才i++,以及每个子串各自的j值++.即i++和每个子串的j++操作时同时的.其中while语句用于 子串j++;循环中的if语句用于每个子串一次匹配完成之后的输出操作,具体用locate函数实现,并且使得j值为1,实现多 次匹配 T.temp=T.base; if(count==tcount) { {++i;} while(T.temp!=T.top) { ++(*T.temp).j; if((*T.temp).j > (*T.temp).length&&(S[i-1]==' '||S[i-1]=='\n')&&(S[i- (*T.temp).length-2]==' '||S[i- (*T.temp).length-2]=='\n')) // 此if语句中的条件是:当前的j 值大与子串的长度,并且主串中的单词与子串需完全相等,避免出现如"his"与"is"的情况 { locate (S,(*T.temp),(i - (*T.temp).length)); (*T.temp).j=1; } T.temp++; } } } 其他函数功能见注释: #include <stdio.h> #include <stdlib.h> #include<alloc.h> #include<process.h> #include<malloc.h> #include<string.h> #include<conio.h>//包含全部所需的头文件 #define STACK_INIT_SIZE 100; #define STACKINCREATEMENT 10; int tcount=0;//定义全局变量,保存输入字符串个数 typedef struct HString{ char *ch; int length; int account; int next[100]; int j; }HString; typedef struct Stack{ HString *base; HString *top; HString *temp; int stacksize; }Stack; //定义两个结构体,实现栈的操作 void InitStack(Stack &S){ S.base=(HString*)malloc(50* sizeof(HString)); if(!S.base)exit(0); S.top=S.base; S.stacksize=50; }//初始化栈 void Push(Stack &S,HString string){ if(S.top-S.base>=S.stacksize){ S.base=(HString *)realloc(S.base,(S.stacksize+10)*sizeof(HString)); if(!S.base)exit(0); S.top=S.base+S.stacksize; S.stacksize+=10; } *S.top++=string; }//每次输入一个字符串,压入栈中 void get_nextval(Stack &stack) { stack.temp=stack.base; while(stack.temp!=stack.top) { int i=1;int length=(*stack.temp).length; (*stack.temp).next[0]=0; int j=0; while(i<=length) {if(j==0||(*stack.temp).ch[i-1]==(*stack.temp).ch[j-1]) {++i;++j; if((*stack.temp).ch[i-1]!=(*stack.temp).ch[j-1]) (*stack.temp).next[i-1]=j; else (*stack.temp).next[i-1]=(*stack.temp).next[j-1]; } else j=(*stack.temp).next[j-1]; } stack.temp++; } } //用改进的算法求解每个子串的next函数值,其算法榆书上的大体相同,只是数组下标有所不同,从0开始 void locate (char S[],HString &str,int i) {int j=0,row=1; str.account++; while(j!=i+1) {if(S[j]=='\n') row++;j++; } printf("the word: %s appears the %d time,in row: %d\n",str.ch,str.account,row); }//定位函数,即每次调用此函数,打印出其出现的次数,以及相应的行数 void Index_KMP(char S[],int n,Stack T,int pos) { int Slength=n; int i =pos ; T.temp=T.base; while( i <Slength){ T.temp=T.base; while(T.temp!=T.top) {if((*T.temp).j != 0 &&S[i-1] !=(*T.temp).ch[(*T.temp).j-1]) { (*T.temp).j = (*T.temp).next[(*T.temp).j-1]; } T.temp++; } T.temp=T.base; int count=0; while(T.temp!=T.top) { if((*T.temp).j==0||S[i-1]==(*T.temp).ch[(*T.temp).j-1]) {count++;} T.temp++; } T.temp=T.base; if(count==tcount) { {++i;} while(T.temp!=T.top) { ++(*T.temp).j; if((*T.temp).j > (*T.temp).length&&(S[i-1]==' '||S[i-1]=='\n')&&(S[i- (*T.temp).length-2]==' '||S[i- (*T.temp).length-2]=='\n')) { locate (S,(*T.temp),(i - (*T.temp).length)); (*T.temp).j=1; } T.temp++; } } } } //此函数用kmp算法执行匹配过程.前面已有注释. 在主函数中,我先把外存中的文件读进来.把它保存到动态分配的数组中,然后在控制台窗口中打印文本文件.输入要 查询的子串,把它压入栈中. void main() { Stack stack; HString string; InitStack(stack); FILE *fp;//定义一个文件指针 int n=0;//变量n用来记录文件中字符的个数 char ch, filename[10]; printf("\n"); printf("Please enter the filename you want to edit:\n"); scanf("%s",filename);//输入想要编辑的文件名 if((fp=fopen(filename,"r"))==NULL)//打开文件 {printf("cannot open file or the file does not exsist!\n"); exit(0);} ch=fgetc(fp); while(ch!=EOF) {n++; ch=fgetc(fp); }//计算字符的个数 rewind(fp);//把文件指针重新指向文件开头 char *str=NULL; str=(char *)calloc(n,1);//动态的开辟一个存放文件的空间,把指针保存在指向字符的指针str中 char *mainstring=str;//把文件首地址保存到mainstring中，用于打印和函数调用 ch=fgetc(fp); while(ch!=EOF) { *str=ch; str++; ch=fgetc(fp); }//为每个新开辟的空间赋值，即一个字节空间存放一个字符 *str='\0';//置最后一个字符为'\0',表明文件结束 fclose(fp);//关闭文件 printf("%s",mainstring);//打印原文本文件 printf("\n"); printf("how many words do you want to edit:\n"); scanf("%d",&tcount); printf("please enter the word:\n"); struct Entry_struct { char name[20]; int length; } entry[20];//用一个结构体数组保存输入的子串 for(int m=0;m<tcount;m++) { scanf("%s",entry[m].name); string.ch=entry[m].name;string.length=strlen(entry[m].name); string.account= 0;string.j=1;// 初始化栈中的各个变量 Push(stack,string);//压入栈中 } get_nextval(stack);//计算每个子串的next函数值 Index_KMP(mainstring,n,stack,1);//执行匹配算法 free(mainstring);//释放空间 } 运行结果演示： Please enter the filename you want to edit: wendang.txt Forrest Gump is the story of an incredibly kind and gentle person who is also what some people might call "mildly retarded." It's true that he is not too smart, but he is very fortunate, because has a mother and friend who love him dearly. Forrest is born and raised in rural Alabama, in the Southern United States. He grows with his mother.Despite his lack of sophistication, and the fact that he was raised far from any major cities, Forrest manages to become personally involved in most of the critical events that take place in American History from the late 1950s until the early 1980s. how many words do you want to edit: 3 please enter the word: most born place the word: born appears the 1 time,in row: 6 the word: most appears the 1 time,in row: 11 the word: place appears the 1 time,in row: 11