题目描述

读入数据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
  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. 题目存在多个括号，以下代码遇到【】则循环匹配其中数据，所以不存在问题

#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
*/