文学研究助手（字符串的查找模式匹配KMP算法）

我自己用C语言写的，用了KMP算法，实现了从文件中查找字符的功能。

#include 
#include 

#define MAXSTRLEN 255         //最大串长
typedef char SString[MAXSTRLEN+1];   //串的定长顺序存储表示
int next[MAXSTRLEN];            //KMP算法中用到的next


void  get_next（SString Tint next[]）   //求next值
{
	int j=1k=0;
	next[1]=0;
    while（j	{
		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 SSString Tint pos）  //KMP算法
{
	int i=posj=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=1j=0k;   //i用于存放行号，j用于存放列号k用于输出格式的控制
	FILE *fp;
	if （!（fp=（fopen（name“r“））））  //打开小说文件
	{
		printf（“Open file error!\n“）;
		exit（0）;
	}

    keys[0]=lenth（keys）;        //求关键字的长度
	get_next（keysnext）;        //求模式串（关键字）每一个字符对应的next值
	printf（“%s\n“&keys[1]）;    //打印关键字
	while （!feof（fp））        //如果还没到小说文件末尾
	{
		k=0;
		fgets（&text[1]MAXSTRLENfp）;     //从小说文件中读取一行字符串，存入text串中
		text[0]=lenth（text）;              //求读入的串的长度

		j=Index（textkeysj+1）;        //调用KMP算法，统计关键字在该行出现的位置，若匹配不成功则返回0
		if （j!=0）
		{printf（“row=%dcol=%d“ij）; k++;}   //若匹配成功则打印行号和列号
		while（j!=0）         //若该行找到了关键字，则继续寻找看是否还能匹配成功
		{
			j=Index（textkeysj+1）;  //调用KMP算法从刚找到的列号后一字符起匹配
			if （j!=0）         
			{printf（“%d“j）; } //若匹配成功，则打印列号
		}
		i++;  //行号加1，在下一行中寻找
		if （k）	printf（“\n“）;	//输出格式控制
	}
	
}



void main（）
{
	char name[50];   //存储输入的小说路径字符串
	SString words[10];   //定义字符串数组，用于存储输入的关键字
	int ni;
	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		scanf（“%s“&words[i][1]）;  //用户一次性输入要查找的关键字，words[i][0]用于存放字符串的长度

	for （i=0;i		find（namewords[i]）;    //对于每一个关键字，调用查找函数进行查找统计



}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2619  2009-03-07 21:10  文学研究助手\文学研究助手.cpp

     文件      12800  2009-05-02 19:33  文学研究助手\要求.doc

     目录          0  2009-05-02 19:34  文学研究助手

----------- ---------  ---------- -----  ----

                15419                    3