数据结构与算法----5.3 匹配字符串

[c++]代码库

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

bool match (string p, string s) 
{
	
	int i, j, m, n ; bool **d;		
	m=p.length(); n=s.length(); 
	d=new bool *[m+1] ;
	
	for ( i= 0 ; i<=m;i++) d[i] =new bool [n+1];
	d[0][0]= true ;
	
	for ( j= 1 ; j<=n;j++) d[0][j]= false ;
	for ( i= 1 ; i<=m;i++)
	{
		if(p[i-1]=='*') d[i][0] =d[i-1][0];
		else d[i][0]= false ;
	}
	for ( i= 1 ; i<=m;i++)
	{
		for ( j= 1 ; j<=n;j++)
			if(p[i-1]=='*')
				d[i][j] = d[i-1][j] || d[i][j-1];
			else if(p[i-1]=='?') d[i][j] =d[i-1][j-1];
			else d[i][j] =d[i-1][j-1] && p[i-1]==s[j-1];			
	}
	return d[m][n];
}
int main()
{
    string y="ABCDEF";
	string x="?B*F";
	string s="123456";
	string p="A*5";
	cout<<"模式字符串x:"<<x<<endl<<"待匹配字符串y:"<<y<<endl;
	cout<<"y"<<(match(x,y)?"符合":"不符合")<<"x"<<endl<<endl;

	cout<<"模式字符串p:"<<p<<endl<<"待匹配字符串s:"<<s<<endl;
	cout<<"s"<<(match(p,s)?"符合":"不符合")<<"p"<<endl;
	return 0;
}