1.cpp

Knuth的快速模式匹配算法改良

//需要用到的库函数
# include <iostream.h>
# include "string.h"
# include <string.h>
# include <stdlib.h>
# include <assert.h>
//STEP 1 : 定义类sting
class string
{
//类string的公有成员
public:
	    //将str和size设为公有，方便以后调用
		char *str;
        int size;
		//用到的成员函数
        int strlen(char *s);
	    string(char *s);
		string substr(int index,int count);
};
//STEP 2 :定义成员函数
//2.1计算字符串s.str的长度
int string::strlen(char *s)
{
    int i=0;
	while(*s!='\0')
	{
		i++;                                          //计数器
		s++;
	}
	return i;                                         //返回字符串长度
}
//2.2转换构造函数：把char *类型转换为string类型
string::string(char *s)
{
	size=strlen(s);                                   //计算字符串的长度
	str=new char[size+1];                             //分配内存
	assert(str!=0);                                   //在分配内存失败时终止
	strcpy(str,s);//把字符串直接拷贝到对象中
}
//2.3从母串s.str提取子串函数，从index开始提取长度为count的子串
string string::substr(int index,int count)
{
	int i;
	int left=size-index;                              //自下标left向右计数到串尾
	string temp="0";
	char *p,*q;
    if(count>left)count=left;                         //若count超过自left以右子串的长度，则把count缩小
	delete [] temp.str;                               //释放原来存储的空间
	temp.str=new char [count+1];
	assert(temp.str!=0);                              //若开辟动态存储空间失败，则退出正常运行
	p=temp.str;                                       //p的内容为指针，指向暂无内容的字符数组首字符处
    q=&str[index];                                    //q的内容为指针，指向标准串str数组下标index处
	for(i=0;i<count;i++) *p++=*q++;                   //将s.str赋值给temp.str
	*p=0;                                             //使temp.str的结尾为'\0'
	temp.size=count;
	return temp;                                      //返回提取出的子串
}
//2.4计算模板串特征向量
int * Next(string p)
{
	int m=p.size;
	int *N=new int[m];                                //开辟动态存储特征向量的空间
	assert(N!=0);                                     //开辟动态空间失败则报错跳出程序
	N[0]=0;                                           //模板串下标j=0的字符特征向量为0
    for (int i=1;i<m;i++)                             //对模板串每一位进行分析
	{
		int k=N[i-1];                                 //根据特称向量的递归定义，假设已知第i-1位特征向量
		while(k>0&&p.str[i]!=p.str[k]&&p.str[i]!='?'&&p.str[i]!='*')
				k=N[k-1];                             //用递归方法计算特征向量
        if (p.str[i]==p.str[k]||p.str[i]=='?'&&p.str[i]!='*')
				N[i]=k+1;
		else N[i]=0;                                  //其他情况，包括第i位为"*"特征值置零
	}
	return N;                                         //返回特征向量数组
}
//2.5模式匹配核心算法，参考书上KMP算法思想并进行了改进
int KMP(string s,string p,int *N,int startindex)
{
                                            
	int lastindex=s.size-p.size;
	if((lastindex-startindex)<0)
	return (-1);                                      //开始匹配位置过大匹配失败
	int i;                                            //指向标准串s的游标
	int j=0;                                          //指向模板串p的游标
    for(i=startindex;i<=s.size;i++)
	{   
		//先讨论只含"?"的情况
		while(p.str[j]!=s.str[i]&&j>0&&p.str[j]!='?'&&p.str[j]!='*')
		{//N循环，不考虑"?"和"*"
           j=N[j-1];//与标准串当前字符匹配的模板串下标
		   i=i-j;
		   //i回溯，根据KMP算法思想在模作最坏的打算，设i的前一位是"?"
		   //由于"?"的通配特性，根据KMP算法思想在模式匹配中"?"的特征值是动态变化的
		   //若用KMP原始算法的N循环来搜索模板串的匹配位置那么一定会出现漏配
		   //根据前面Next函数的定义，不妨使用回溯的方法，让i回到i-j位并让j=0
		   //这时标准串的第i位又重新与模板串的起始位匹配
		   //这样避免讨论"?"的特征值
		   j=0;                                       //使模板串的首位对准标准串回溯的后的第i位
		};
		if(p.str[j]==s.str[i]||p.str[j]=='?'&&p.str[j]!='*')
	    j++;
		if(j==p.size&&p.str[j]!='*')
		{
			return (i-j+1);                           //匹配成功返回标准串匹配模板串的下标位置
            break;
		}
		//再讨论遇到"*"号的情况
		//这样做的原因一方面是此时"*"前的模板串已经与标准串匹配
		//另一方面是为了方便后面可以用递归方法进行模式匹配
		if(p.str[j]=='*')
		{
			string s1="0",p1="0";                     //声明两个string型变量，用于存放"*"后面的模板串与标准串
			int ls=s.strlen(s.str),lp=p.strlen(p.str);//计算"*"后标准串与模板串长度
		    s1=s.substr(i+1,ls-i-1);                  //将"*"后的标准串取出，另存为s1
            p1=p.substr(j+1,lp-j-1);                  //将"*"后的模板串取出，另存为p1
			int *M=Next(p1);                          //计算新模板串p1的特征向量，并将其存到数组M中
			if(KMP(s1,p1,M,0)!=-1&&p.str[0]!='*')return i-j+1;
			//用递归的方法对s1与p1进行模式匹配，即遇见"*"便将原模板串以"*"为界一分为二
			//对"*"后的标准串与模板串进行模式匹配，若最终匹配成功便返回标准串匹配模板串的下标位置
			if(KMP(s1,p1,M,0)!=-1&&p.str[0]=='*')return 0;
			//对于"*"在第一位的情况要特殊考虑，这时如果"*"后的标准串与模板串模式匹配成功则返回0
		}
	}
	return (-1);                                      //整个模式匹配失败
}
//STEP 3 ：模式匹配算法主程序 
void main()
{
	char s[100],p[100];                               //声明两个字符型数组，用来存放标准串与模板串
	int k;
	cout<<"*******************模式匹配算法*******************";
	cout<<"\n";
	cout<<"输入标准串 S : ";
	cin>>s;
	cout<<"输入模板串 P : ";
	cin>>p;
    cout<<"设定搜索起始下标 : i = ";
	cin>>k;
    string S=s,P=p;                                   //将输入的char型标准串与模板串转换为自定义的string型
    int *N=Next(P);                                   //调用Next函数
	int K=KMP(S,P,N,k);                               //调用KMP函数
	cout<<"标准串匹配模板串的下标位置为 : i = ";
	cout<<K;
	cout<<"\n";
	if(K!=-1) cout<<"模 式 匹 配 成 功!";
	else cout<<"模 式 匹 配 失 败！"; 
	cout<<"\n";
    
}