博客

字符串匹配

来源：北京航空航天大学

题目描述

读入数据string[ ]，然后读入一个短字符串。要求查找string[ ]中和短字符串的所有匹配，输出行号、匹配字符串。匹配时不区分大小写，并且可以有一个用中括号表示的模式匹配。如“aa[123]bb”，就是说aa1bb、aa2bb、aa3bb都算匹配。

输入描述:

输入有多组数据。 每组数据第一行输入n(1<=n<=1000)，从第二行开始输入n个字符串（不含空格），接下来输入一个匹配字符串。

输出描述:

输出匹配到的字符串的行号和该字符串（匹配时不区分大小写）。

输入

4
Aab
a2B
ab
ABB
a[a2b]b

输出

1 Aab
2 a2B
4 ABB

这道题不难，但是真的卡了好久！思路和注意点:

1. 用tmp标记是否进入括号匹配阶段。

2.如果匹配成功，就直接跳到’]’的后面(注意是后面)，所以while循环以后必须要再对a_count++。

3.遍历完待匹配字符串后，必须看模式串是否也结束了（虽然样例似乎没有卡这个）。

关于Visual Studio单步调试：

1. F9增加断点（或手动）。

2. 局部变量请在调试——>窗口——>自动窗口（Ctrl+Alt+V,A）打开。

3. 注意逐语句和逐过程的区别。如果不关心某些库函数的过程，选择跳出。

#include<bits/stdc++.h>
using namespace std;
bool isLetter(char c)
{
	if(c>='a'&&c<='z'||c>='A'&&c<='Z') return true;
	else return false;
}
bool equal(char a,char b)
{
	if(a==b) return true;
	if(isLetter(a)&&isLetter(b)&&abs(a-b)==32) return true;
	else return false;
}
bool judge(string s,string a)//s待匹配字符串,a目标字符串 
{
	//Aab a[a2b]b 
	int s_count=0;int a_count=0;
	bool flag=true;
	bool tmp=false;
	while(s_count<s.length()){
		if(!tmp&&equal(s[s_count],a[a_count])){
			s_count++;a_count++;
		}
		else if(!tmp&&a[a_count]=='['){
			a_count++;tmp=true;
		}
		else if(tmp){
			if(equal(s[s_count],a[a_count])){
				s_count++;
				while(a[a_count]!=']'){
					a_count++;
				} 
				a_count++;//特别注意!!!while语句执行结束后a[a_count]对着的是']'，此时必须a_count++跳过它! 
				tmp=false;
			}
			else if(tmp&&a[a_count]==']'){
				flag=false;
				break;
			}
			else a_count++;
		}
		else {
			flag=false;break;
		}
	} 
	if(flag&&a_count==a.length()) return true;
	else return false;
}
int main(void)
{
	string s[1001];
	string a;
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>s[i];
		}
		cin>>a;
		for(int i=0;i<n;i++){
			if(judge(s[i],a)){
				cout<<i+1<<" "<<s[i]<<endl;
			}
		}
	}
	return 0;
 }