题解 | #字符串匹配#

/**
KMP的回溯由pattern[前]==pattern[后]变成了pattern[前]包含pattern[后]~
其余都是KMP板子代码啦~
**/
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
bool contains(vector<char>& vc, char c){
    bool found = false;
    for(char pitem:vc){
        if(pitem == c||pitem == c-'a'+'A'||pitem == c+'a'-'A'){
            // 有匹配
            found = true;
            break;
        }
    }
    return found;
}
bool contains(vector<char>& container_k, vector<char>& contained_j){
    bool found = true;
    if(contained_j.size()>container_k.size()) return false;
    for(char pitem:contained_j){
        if(!contains(container_k, pitem)){
            found=false;
            break;
        }
    }
    return found;
}
int nxt[1000];
int main(){
    int curr=1, prev=0, periods;
    string s;
    vector<string> strs;
    vector<vector<char>> pattern;
    cin>>periods;
    for(int i=0;i<periods;++i){
        cin>>s;
        strs.push_back(s);
    }
    cin>>s;
    for(int i=0;i<s.size();++i){
        if(s[i] == '['){
            vector<char> stack;
            ++i;
            while(s[i]!=']'){
                stack.push_back(s[i]);
                ++i;
            }
            pattern.push_back(stack);
        }else{
            pattern.push_back(vector<char>(1, s[i]));
        }
    }
    // KMP Construct
    int pL = pattern.size();
    nxt[0]=-1;
    for(int j=0,k=-1;j<pL;++j){
        if(k==-1||contains(pattern[k], pattern[j])){
            ++j;
            ++k;
            if(contains(pattern[k], pattern[j])){
                nxt[j] = nxt[k];
            }else{
                nxt[j] = k;
            }
        }else{
            k=nxt[k];
        }
    }
    for(int count=0;count<strs.size();++count){
        string str = strs[count];
        // KMP Matching
        int i=0, j=0;
        while(i<str.size()&&j<pL){
            if(j==-1||contains(pattern[j], str[i])){
                ++j;
                ++i;
            }else{
                j=nxt[j];
            }
        }
        if(j==pL){
            cout<<count+1<<" "<<str.substr(i-j,pL)<<endl;
            continue;
        }
    }
    return 0;
}