字符串匹配
给定一个包含 n 个字符串的字符串数组 s1,s2,…,sn 和一个短字符串 p，找出字符串数组中所有能够和短字符串匹配的字符串。
匹配时不区分大小写，短字符串中可能包含若干个用中括号表示的模式匹配。
例如，对于 aa[123]bb，字符串 aa1bb、aa2bb、aa3bb 均可与其匹配。
输入格式
第一行包含整数 n，表示字符串数组中的字符串个数。
接下来 n 行，第 i 行包含一个字符串表示 si。
最后一行，包含一个字符串表示 p。
输出格式
输出可以匹配的字符串的下标和该字符串。
数据范围
1≤n≤1000,
si 的长度不超过 10,
p 的长度不超过 50,
所有字符串中只包含大小写字母、数字、[]。
输入样例：
4
Aab
a2B
ab
ABB
a[a2b]b
输出样例：
1 Aab
2 a2B
4 ABB
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
const int M = 2e5+10;
int n,m;
vector<string> vs;
string p;
bool match(string t){
int i,j;
for(i = 0,j = 0; j <= p.size() - 1 && i <= t.size() - 1; i ++,j ++ ){
if(p[j] == '['){
bool f = 0;
j ++;
while(p[j] != ']'){
if(p[j] == t[i])f = 1;
j ++;
}
if(!f)return 0;
}
else if(p[j] != t[i])return 0;
}
if(j != p.size() || i != t.size())return 0;
return 1;
}
void solve(){
cin >> m;
while(m -- ){
string s;
cin >> s;
vs.push_back(s);
}
cin >> p;
transform(p.begin(), p.end(),p.begin(),::tolower);
for(int i = 0; i <= vs.size() - 1; i ++ ){
string t = vs[i];
transform(t.begin(), t.end(),t.begin(),::tolower);
if(match(t))cout << i + 1 << " " << vs[i] << nl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
注意
- 每个字符串只匹配一次
- 如果用组合的方法枚举p的每一种情况再进行匹配会tle