00207047kmp.cpp

使用著名的KMP模式匹配算法进行字符串匹配

#include <iostream>
#include <string>
using namespace std;

void Next(string &Pattern,int *N)
{                                //根据kmp算法得出的计算特征数组的函数，Pattern为模式串，N存储特征数组,本函数将处理Pattern含“？”的情况
	int strlen=Pattern.size();
	int i=1;
	N[0]=0;
	for(;i<strlen;i++)                                 //循环求特征向量
	{
		int k=N[i-1];
		while(k>0&&Pattern[i]!=Pattern[k])
		{
			if(Pattern[i]=='?'||Pattern[k]=='?')       //当不匹配的字符是由于“？”引起的情况发生时
			{
				N[i]=k+1;                              //特征值视为匹配
				break;                                 //匹配后进行下一位比较，退出本循环，break语句与下面的continue连用，避免了goto语句的出现
			}
			else 
				k=N[k-1];
		}
		if((Pattern[i]=='?'||Pattern[k]=='?')&&(k!=0)&&Pattern[i]!=Pattern[k]) //由于“？”的关系，进行下一位比较
			continue;
		if((Pattern[k]==Pattern[i]))                   //当前位匹配
			N[i]=k+1;
		else               
		{ 
			if(Pattern[0]=='?'||Pattern[i]=='?')       //不匹配时若第一比较位为“？”特征值为1
				N[i]=1;
			else                                       //否则第一比较位特征值为0
				N[i]=0;
		}
	}
}


void truncation(string & Pattern,string * str)
{                                 //将模式串以“*”为间隔前后分割，存入string型的数组中str，本函数处理含“*”的情况
	int i=0,j=0,k=0;  
	if(Pattern[i]=='*')          //特殊情况的处理：第一个字符就是“*”
	{
		i=1;
		k=1;
	}
	int length=Pattern.size();
	if(Pattern[length-1]!='*') //在串末尾加上一个“*”，则原有“*”前后的字串可以同等考虑（放入str中的字串为两个“*”之间或“*”与开头之间的部分）
		Pattern[length]+='*';  //这个方法是我和吕国成同学讨论的结果，在此对他表示感谢
	
	while(Pattern[i]!='\0')
	{                           //循环截取子串
		if(Pattern[i]!='*')     //不是“*”则游标i后移
			i++;
		else                    //遇到“*”后，从前一个“*”（或开头）后截取到这一个“*”前，存入str[j]中
		{
			str[j]=Pattern.substr(k,i-k); 
			k=++i;
			j++;
		}
	}
}





int KMP_FindPat(string &Target,string &Pattern,int startindex)
{    //利用改进的kmp算法进行模式匹配，Target为目标串，Pattern为模式串，startindex表示的是起始位置，如果成功就返回匹配位置，失败后返回-1
	int len=Pattern.size();
	int * N;
	N=new int[len];                                   //动态分布空间，用于存放特征值向量
	Next(Pattern,N);                                  //调用Next()函数
	int h=-1;
	int LastIndex=Target.size()-Pattern.size();
	if(LastIndex<=startindex)
		return h=-1;
	
	int i=startindex;
	int j=0;
	if(Pattern[startindex]=='?')                     //Pattern的第一个字符为“？”的处理情况
	{
		i=startindex+1;
		j++;
	}
	for(;i<Target.size();i++)
	{
		
		while(Pattern[j]!=Target[i]&&j>0)
		{
			if(Pattern[j]=='?')
			{                                        //由于“？”引起的字符不匹配被当作匹配，跳出while循环
				j++;
				break;
			}
			j=N[j-1];
		}
		
		if((Pattern[j]=='?')&&j!=Pattern.size()&&j!=0)
			continue;                                //这个语句的实现与Next函数中一样，与break一起避免了goto的出现
		if(j==0&&Pattern[0]=='?')
			j++;		
		if(Pattern[j]==Target[i])
			j++;
		if(j==Pattern.size())
		{   
			return 
				h=i-j+1;                             //匹配成功，返回匹配地址值
			break;
		}
	}	
	if(h==-1)
		return h;
}



void main()
{
	cout << "***********************************************************************" << endl;
	cout << "***********************************************************************" << endl;
	cout << "************         Welcome to Use My Program!!!          ************" << endl;
	cout << "************        Please follow the instructions         ************" << endl;
	cout << "***********************************************************************" << endl;
	cout << "***********************************************************************" << endl;
	string Pattern;
	string Target;
	cout << "请输入目标串: ";
	cin >> Target;
	cout << "请输入匹配串: ";
	cin >> Pattern;
	int j,k;
	string * str;
	str=new string[128];
	truncation(Pattern,str);                         //截取字串放入str中
	int tag = 1;                                     //若匹配成功为1，失败为0
	for(int i=0;str[i]!="\0";i++)
	{
		int h=KMP_FindPat(Target,str[i],k=0);
		if(Target==Pattern)                          //处理特殊情况：Pattern与Target相等，匹配位为0
			h=0;
		j=h;
		if(h==-1)                                    //h为-1，则说明匹配失败
		{
			tag = 0;
			cout << endl << "Bad Luck!!!" << endl;
			cout<<"Pattern Failed!!!"<<endl;
			cout << "Please tre again later." << endl << endl;
			break;
		}
		k+=str[k].size();                            //比较被截取的下一段字串，开始位置为k之后的str[k].size处
	}
	if(tag==1)
	{
		j=KMP_FindPat(Target,str[0],k=0);            //j为被截取的第一位字串的起始匹配位，即为整个Pattern的起始匹配位
		cout << endl << "Well Down!!!" << endl;
		cout<<"Pattern Succeeded"<<endl;
	    cout<<"The first paterned position is "<< j <<endl;
	}
}



//我保证没有抄袭他人程序!!!