3_4.cpp

快速模式匹配算法

// 我真诚地保证：
    
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

// 在此，我感谢课本中的例子代码对我的启发和帮助。下面的报告中，我还会具体地提到
// 他们在各个方法对我的帮助。
 
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。

// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// <学生姓名>刘涛<00348297>

/*
文件名称：3_4.cpp
项目名称：上机3_4
创建者：刘涛
创建时间：2004-9-27
最后修改时间：2004-9-28
功能： 用户输入一个目标对象S，和一个模板P，程序从S中找到与P匹配的第一个子串，
		并输出子串的起始位置
文件中的函数名称和简单功能描述：FindPat(),从S中找到与P匹配的第一个子串并输出
								子串的起始位置
文件中定义的全局变量和简单功能描述：无
文件中用到的他处定义的全局变量及其出处：无
与其他文件的依赖关系：依赖STL实现
*/


#include<iostream>
#include<string>
#include<assert.h>

using namespace std;

int FindPat(string , string , int );

//参照课本算法3.14
int FindPat(string S, string P, int startindex){
	int LastIndex = S.size() - P.size();
	if( ( LastIndex - startindex ) < 0 )
		return (-1);
	int i = startindex, j = 0;
	while ( i < S.size() && j < P.size() ) {
		if ( P[j] == S[i] ){
			i ++;
			j ++;
		}

		//与课本算法不同的补充处理部分，考虑'?'、'*'的情况
		else if ( P[j] == '?' ){	//此时若P中当前字符为'?'
			i ++;					//则跳过当前位置，继续往后匹配
			j ++;
			continue;
		}
		else if ( P[j] == '*' ){
			i ++;
			j ++;

			//取出P中'*'后的字符, 取出的S中对应于'*'的字符之后的所有字符
			//进行新的匹配
			int a = FindPat( S.substr( i, (S.size()-i) ), 
							P.substr( j, (P.size()-j) ), 0);
			a ++;
			//此时a的值表示'*'所表示的字符个数

			//不单独取出S中的后面部分子串，从位置i开始比较
			int b = FindPat( S, P.substr( j, (P.size()-j) ), i);
			//b指向S中'*'对应部分之后的第一个字符
			//例如S="monsters", P="n*r", 则b表示S中r的位置,即b=6

			if( b!= -1 )	//如果可以匹配
				return ( b - a - ( j - 1 ) );// (j-1)表示P中'*'前的字符数
		}

		else {
			i = i - j + 1;
			j = 0;
		}
	};
	if( j >= P.size() )
		return ( i - j );
	else
		return (-1);
}

void main(){
	string S, P;
	cin >> S;
	cin >> P;
	int iPosition = 0;
	//若S中有多个匹配子串，则循环可以把它们都找出来
	for(int i = 0; iPosition != -1; i++ ){
		iPosition = FindPat( S, P, ++iPosition);
		if( !(i != 0 && iPosition == -1) )
		cout << iPosition << endl;
	}
}