字符串匹配
题目描述
读入数据string[ ]，然后读入一个短字符串。要求查找string[ ]中和短字符串的所有匹配，输出行号、匹配字符串。匹配时不区分大小写，并且可以有一个用中括号表示的模式匹配。如“aa[123]bb”，就是说aa1bb、aa2bb、aa3bb都算匹配。
输入描述:
输入有多组数据。 每组数据第一行输入n(1<=n<=1000)，从第二行开始输入n个字符串（不含空格），接下来输入一个匹配字符串。
输出描述:
输出匹配到的字符串的行号和该字符串（匹配时不区分大小写）。
示例1
输入
4 Aab a2B ab ABB a[a2b]b
输出
1 Aab 2 a2B 4 ABB
系统函数：
char *;
strupr 字符串转换为大写
strlwr 字符串转换为小写
string
char *;
strupr 字符串转换为大写
strlwr 字符串转换为小写
string
tmpstr.resize(str[i].size()); //预分配大小
transform(substr.begin(),substr.end(),str.begin(),::tolower); //字符串变小写
transform(substr.begin(),substr.end(),str.begin(),::toupper); //字符串变大写
思路：
1.主串模式串串变小写
2.遇到【】循环匹配，移动指针
3.朴素模式匹配
其他思路：
1.正则表达式 https://blog.csdn.net/philpanic9/article/details/88141305?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
#include<regex>
regex r(substr, regex::icase); regex::icase 不区分大小写
regex_match(str[i], r) 完全匹配
regex_search(str[i],r) 部分匹配
牛客网测试用例问题归纳：
1. 题目默认主串模式串长度相等，以下代码考虑了KMP
2. 题目存在多个括号，以下代码遇到【】则循环匹配其中数据，所以不存在问题
transform(substr.begin(),substr.end(),str.begin(),::tolower); //字符串变小写
transform(substr.begin(),substr.end(),str.begin(),::toupper); //字符串变大写
思路：
1.主串模式串串变小写
2.遇到【】循环匹配，移动指针
3.朴素模式匹配
其他思路：
1.正则表达式 https://blog.csdn.net/philpanic9/article/details/88141305?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
#include<regex>
regex r(substr, regex::icase); regex::icase 不区分大小写
regex_match(str[i], r) 完全匹配
regex_search(str[i],r) 部分匹配
牛客网测试用例问题归纳：
1. 题目默认主串模式串长度相等，以下代码考虑了KMP
2. 题目存在多个括号，以下代码遇到【】则循环匹配其中数据，所以不存在问题
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
int main(void){
string str[1000],substr,tmpstr;
int n,k,i,j,m;
int subcount;
bool flag;
while(cin >> n){
getline(cin,tmpstr); //第一行余留部分""
for(int i = 0; i < n; ++i){
getline(cin, str[i]);
}
getline(cin, substr);
//计算子串长度
subcount = 0;
for(i = 0; i < substr.size(); ++i){
if(substr[i] == '['){
while(substr[++i] != ']');
}
subcount++;
}
//子串变小写
transform(substr.begin(),substr.end(),substr.begin(),::tolower);
//朴素模式匹配
for(i = 0; i < n; ++i){
k = 0; flag = false;
//先预设一个和str相同大小的字符串，每个字符串用小写相比较，用原字符输出
tmpstr.resize(str[i].size());
transform(str[i].begin(),str[i].end(),tmpstr.begin(),::tolower);
for(j = 0, m = j; j < tmpstr.size() && k < substr.size(); ++j){
if(substr[k] == '['){
while(substr[++k] != ']'){
if(substr[k] == tmpstr[j]){
flag = true;
}
}
k++;
if(flag) continue;
else{
j = ++m;
k = 0;
}
}else if(substr[k] == tmpstr[j]){
k++;
}else{
j = ++m;
k = 0;
}
}
if(k == substr.size()){
cout << i + 1 << ' ' ;
for(int x = j - subcount; x < j; ++x){
cout << str[i][x];
}
cout << endl;
}
}
}
return 0;
}
/*
4
Aab
a2B
ab
ABB
a[a2b]b
1 Aab
2 a2B
4 ABB
2
Asdbgs
yIDCgs
D[CB]gs
1 dbgs
2 DCgs
*/
美的集团公司福利 878人发布