www.pudn.com > KMP.rar > 文学研究助手.cpp, change:2009-03-07,size:2619b


#include <stdio.h> 
#include <stdlib.h> 
 
#define MAXSTRLEN 255         //最大串长 
typedef char SString[MAXSTRLEN+1];   //串的定长顺序存储表示 
int next[MAXSTRLEN];            //KMP算法中用到的next 
 
 
void  get_next(SString T,int next[])   //求next值 
{ 
	int j=1,k=0; 
	next[1]=0; 
    while(j<T[0]) 
	{ 
		if(k==0||T[k]==T[j])   
		{ 
			++j;++k;  
			if(T[j]!=T[k]) next[j]=k; 
			else next[j]=next[k]; 
		} 
		else k=next[k]; 
	} 
} 
 
 
int Index(SString S,SString T,int pos)  //KMP算法 
{ 
	int i=pos,j=1; 
   while(i<=S[0]&&j<=T[0]) 
   { 
	   if(j==0||S[i]==T[j]) {++i;++j;} 
	   else 
		   j=next[j]; 
   } 
   if (j>T[0]) return (i-T[0]); 
   else 
	   return 0; 
} 
 
int lenth(SString str)    //求串长 
{ 
	int i=1; 
	while(str[i]) i++; 
	return(i-1); 
} 
 
void find(char name[],SString keys)  //查找函数,该函数是整个程序最重要的部分,对于输入的每一个 
{                                    //要查找的关键字,从小说文件中逐行读取字符串查找 
	SString text;  //存放从小说文件读取的一行字符串       
	int i=1,j=0,k;   //i用于存放行号,j用于存放列号,k用于输出格式的控制 
	FILE *fp; 
	if (!(fp=(fopen(name,"r"))))  //打开小说文件 
	{ 
		printf("Open file error!\n"); 
		exit(0); 
	} 
 
    keys[0]=lenth(keys);        //求关键字的长度 
	get_next(keys,next);        //求模式串(关键字)每一个字符对应的next值 
	printf("%s\n",&keys[1]);    //打印关键字 
	while (!feof(fp))        //如果还没到小说文件末尾 
	{ 
		k=0; 
		fgets(&text[1],MAXSTRLEN,fp);     //从小说文件中读取一行字符串,存入text串中 
		text[0]=lenth(text);              //求读入的串的长度 
 
		j=Index(text,keys,j+1);        //调用KMP算法,统计关键字在该行出现的位置,若匹配不成功则返回0 
		if (j!=0) 
		{printf("row=%d,col=%d",i,j); k++;}   //若匹配成功则打印行号和列号 
		while(j!=0)         //若该行找到了关键字,则继续寻找看是否还能匹配成功 
		{ 
			j=Index(text,keys,j+1);  //调用KMP算法从刚找到的列号后一字符起匹配 
			if (j!=0)          
			{printf(",%d",j); } //若匹配成功,则打印列号 
		} 
		i++;  //行号加1,在下一行中寻找 
		if (k)	printf("\n");	//输出格式控制 
	} 
	 
} 
 
 
 
void main() 
{ 
	char name[50];   //存储输入的小说路径字符串 
	SString words[10];   //定义字符串数组,用于存储输入的关键字 
	int n,i; 
	printf("Please input the name of the novel:\n"); 
	scanf("%s",name); 
	printf("How many words do you want to find?(n<10)\n"); 
	scanf("%d",&n); 
	printf("Please input the words you want to find:\n"); 
	for (i=0;i<n;i++) 
		scanf("%s",&words[i][1]);  //用户一次性输入要查找的关键字,words[i][0]用于存放字符串的长度 
 
	for (i=0;i<n;i++) 
		find(name,words[i]);    //对于每一个关键字,调用查找函数进行查找统计 
 
 
 
}