字符串匹配（北航机试题）_读入n个字符串,然后读入一个短字符串reg。要求查找这些字符串中和短字符串reg

最近在刷王道机试题，所以本题来自王道机试指南

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

输入描述

第一行输入N(1<=N<=1000)
第二行开始输入N个文本串（不含空格）
接下来输入一个模式串

输出描述

输出匹配到的文本串的行号和匹配的字符串（由于题目描述不完整，这里假设输出的是整个文本串）

输入样例

4
Aab
a2B
ab
ABB
a[a2b]b
1
2
3
4
5
6

输出样例

1 Aab
2 a2B
4 ABB
1
2
3

思路

这题要注意的几个要点

1. 运用KMP算法
2. 匹配不区分大小写
3. 对模式串中的 " [] " 的处理

• 有关KMP算法，可以看这篇博客，图文讲解非常详细：KMP算法详解

• 为了处理不区分大小写的匹配，有两种比较简单的办法，第一种是定义一个判断函数来代替等号，在函数中对大小写进行处理；第二种是在匹配时直接将字符串全转换为小写。
  这里采取第二种做法，会用到transform()函数，有关transform()函数的介绍：transform()函数简介

• 对 " [] " 的处理：我将位于 " [] " 内的每个字符，分别与原字符串其他部分进行拼接，生成一个模式串集合。在匹配时将文本串与模式串集合中的每个模式串都进行匹配，若匹配成功，输出匹配结果。

#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

/*
    题目描述：
        字符串匹配
            不区分大小写，同时模式串可以带中括号，例如a[ab]c与aac和abc都匹配。
*/
void build_next(string pattern, int* next){ //构造next表
    int j = 0;
    int i = -1;
    next[0] = -1;
    while( j < pattern.size()){
        if( i < 0 || pattern[i] == pattern[j]){
            i++;
            j++;
            next[j] = i;
        }
        else i = next[i];
    }
}

bool KMP(string pattern, string text){
    int next[pattern.size()];
    
    //全转换为小写
    transform(pattern.begin(),pattern.end(),pattern.begin(),::tolower);
    transform(text.begin(),text.end(),text.begin(),::tolower);

    build_next(pattern, next);
    int i = 0, j = 0;
    while(i < pattern.size() && j < text.size()){
        if(i < 0 || pattern[i] == text[j]){
            i++;
            j++;
        }
        else i = next[i];
    }
    if(i == pattern.size()){
        return true;
    }
    else{
        return false;
    }
}

int main(){
    int N; //文本串的个数
    cin>>N;
    vector<string> text;
    string pattern;
    vector<string> pat_set;
    while(N--){
        string t;
        cin>>t;
        text.push_back(t);
    }
    cin>>pattern;
    if(pattern.find('[') != string::npos){//处理带括号的模式串
        int left = pattern.find('[');
        int right = pattern.find(']');
        int num_of_pattern = right-left-1;
        for(int i = 1;i<=num_of_pattern;i++){
            string s = pattern.substr(0,left) + pattern[left+i] + (right == pattern.size()?"":pattern.substr(right+1,pattern.size())); // 这里处理了右括号是最后一个字符的特殊情况
            pat_set.push_back(s);
        }
    }
    else{
        pat_set.push_back(pattern);
    }
    for(int i = 0; i < text.size(); i++){
        for(int j = 0; j < pat_set.size(); j++){
            if(KMP(pat_set[j], text[i])){
                cout<<i+1<<" "<<text[i]<<endl;
                break;
            }
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84