kmp.cpp

自己编写的字符串匹配算法-经典的KMP算法

//字符串匹配算法
//KMP算法,区分大小写
#include<stdio.h>
#include<stdlib.h>

#define pat_length 34  //模式字符串长度

int compare(unsigned char *t, unsigned char *p);
int next(int j);                    //分析已匹配真子串长度
int sub_stream(int location, int length);  //分析真子串的子函数

unsigned char pat[pat_length+1]={"consideration in Utah and Michigan"};  //存储模式数据，最后一位存储字符串终止符
unsigned char test[pat_length+1]={0};  //存储与模式等长的文本数据
void main()
{
	int i;
	int match;  //字符比较的返回值
	int num=0;    //已匹配真子串长度
	unsigned char *t,*p;   //分别指向test数组和pat数组

	FILE *fp;
	if((fp=fopen("e:/c projects/kmp_algorithm/test.txt","r"))==NULL)  //打开文本文件
	{
		printf("Cannot open test file!");
		exit(1);
	}
	fread(test,sizeof(unsigned char),pat_length,fp);

    do
	{
		t=test;
		p=pat;

		match=compare(t,p);

		//如果字符串匹配则结束循环
		if(match==pat_length)
		{
			printf("Stream match!!!\n");
			break;
		}
		else  //否则分析当前已匹配字符的个数,并使文本数据左移相应个单元
		{
			num=next(match);

			if(num==-1)   //向左滑行一位
			{
				for(i=0;i<pat_length-1;i++)
				    test[i]=test[i+1];
		        fread(&test[pat_length-1],sizeof(unsigned char),1,fp); 

		    	if(test[pat_length-1]=='\n')  //如果最后一位是换行符，则用空格符代替换行符
				    test[pat_length-1]=' ';
//				printf("nest[j]==-1........\n");
			}
			else if(num==0)  //滑行到不匹配字符的当前位
			{
				for(i=match;i<pat_length;i++)
				    test[i-match]=test[i];
		        fread(&test[pat_length-match],sizeof(unsigned char),match,fp); 

		    	for(i=pat_length-match;i<pat_length;i++)   //如果中间存在换行符，则用空格符代替换行符
				{
				    if(test[i]=='\n')  
				        test[i]=' ';
				}
//				printf("nest[j]==0........\n");
			}
			else   //存在真子串，滑行相关长度单元
			{
				for(i=num;i<pat_length;i++)
				    test[i-num]=test[i];
		        fread(&test[pat_length-num],sizeof(unsigned char),num,fp); 

		    	for(i=pat_length-num;i<pat_length;i++)   //如果中间存在换行符，则用空格符代替换行符
				{
				    if(test[i]=='\n')  
				        test[i]=' ';
				}
//				printf("nest[j]==k........\n");
			}
		}
	}while(!feof(fp));

	if(match!=pat_length)
		printf("Stream not match......!!!\n");

	fclose(fp);
	return ;
}



//字符串比较函数，返回匹配字符的个数
int compare(unsigned char *t, unsigned char *p)
{
	int i;
	unsigned char a,d;
	for(i=0;i<pat_length;i++)
	{
		a=*t;
		d=*p;
//		printf("d=%c\n",d);
//		printf("a=%c\n",a);
		if(d==a)
		{
			t++;
			p++;
		}
		else
			break;
	}
	return i;  
}

//分析已匹配真子串长度
int next(int j)
{
	int i;
	int tr;  //判断是否包含真子串
	int sub_length=0;  //真子串长度
	unsigned char *pt;

	pt=pat;
	if(j==0)  //表示已匹配字符个数为0
		sub_length=-1;
	else
	{
		for(i=1;i<j;i++)
		{
			if(pat[0]==pat[i])
			{
				tr=sub_stream(i,j);
				if(tr)  //最先得到的真子串肯定是最长的，故可以停止寻找
				{
					sub_length=i;   //返回真子串头所在位置
//				    printf("sub_stream........\n");
					break;
				}
			}
		}
		if(i==j)  //表示没有真子串
			sub_length=0;
	}

	return sub_length;
}


//分析真子串的子函数
//如果包含真子串，返回1，否则返回0
int sub_stream(int location, int length)
{
	int k,t;
	for(k=0,t=location; k<(length-location),t<length; k++,t++)
	{
		if(pat[t]!=pat[k])
			break;
	}

    if(t==length)  //表示是真子串
		return 1;
    else
		return 0;
}