题解 | #攻击识别#

题目的关键是判断输入的串是否是模式串仅插入一次得到的，所以在从前往后遍历发现不匹配时再从后向前遍历查找有没有发现第二次不匹配（也就是第二次插入片段）。如果发现第二次不匹配，那么不满足题目要求，不是攻击包，如果只有一次不匹配，那么就是攻击包。

#include <bits/stdc++.h>

using namespace std;

bool is_match(const string &recv, const string &pat) {
    //剪枝
    if (recv.size() < pat.size())
        return false;
    else if (recv == pat)
        return false;

    int r_p = 0, p_p = 0;   //从前向后遍历的指针
    while (r_p < recv.size() && p_p < pat.size()) {
        if (recv[r_p] != pat[p_p]) {    //当发生了不匹配时
            int rr_p = recv.size() - 1, rp_p = pat.size() - 1;  //从后向前遍历的指针
            while (rr_p >= r_p && rp_p >= p_p) {
                if (recv[rr_p] != pat[rp_p])
                    //因为已经发生了不匹配的情况，也就是插入了一次，此时两个串都从后向前匹配，如果再次发生不匹配的情况，就说明
                    //又发生了一次插入操作，那么就不符合题目的条件，该串不是攻击包。
                    return false;

                --rr_p;
                --rp_p;
            }
            //如果从后向前匹配成功遍历完成，那么就说明该串只在模式串的基础上进行了一次插入操作，是攻击包
            return true;
        } else {
            ++r_p;
            ++p_p;
        }
    }
    return true;
}

int main() {
    int pat_num;
    cin >> pat_num;
    vector<string> pattern(pat_num);    //模式串数组
    for (int i = 0; i < pat_num; ++i) {
        cin >> pattern[i];
    }

    int recv_num;
    cin >> recv_num;
    string recv;
    for (int i = 0; i < recv_num; ++i) {
        cin >> recv;    //收到的串

        bool is_find = false;   //是否是攻击包
        for (const auto &p: pattern) {
            if (is_match(recv, p)) {
                cout << "YES" << endl;
                is_find = true;
                break;
            }
        }

        if (!is_find) {
            cout << "NO" << endl;
        }

    }

    return 0;
}