优化C++多子串查找算法 解决OJ提交时间超限问题

问题根因 #

当前代码的核心性能瓶颈在于匹配逻辑：

• 你已经做了ios_base::sync_with_stdio(false);和stringstream缓存输出的优化，输入输出部分没有性能问题，问题出在逐个匹配的逻辑上。
• 每匹配一个子串就调用一次strstr，最坏时间复杂度为O(nm)，n为主串长度，m为当前模式串长度。如果单个测试用例有k个模式串，总时间复杂度就会达到O(kn*m)，当主串长度大、模式串数量多的时候，运算量会远超时间限制。

优化方案 #

推荐使用AC自动机算法，这是竞赛中多模式串匹配的标准解法，仅需遍历一次主串就能完成所有模式串的匹配，总时间复杂度降至O(n + 所有模式串总长度)，完全可以满足该题的时间要求。

优化后代码 #

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <sstream>
using namespace std;

const int MAXN = 256; // 兼容所有ASCII字符，若确认仅小写字母可改26进一步提速
struct Node {
    Node* next[MAXN];
    Node* fail;
    int idx; // 标记当前节点对应哪个模式串，-1表示不是模式串结尾
    Node() {
        memset(next, 0, sizeof(next));
        fail = nullptr;
        idx = -1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    stringstream ss;
    int testCnt;
    cin >> testCnt;
    while (testCnt--) {
        string s;
        int patternCnt;
        cin >> s >> patternCnt;
        vector<string> patterns(patternCnt);
        vector<bool> exist(patternCnt, false);
        // 构建AC自动机前缀树
        Node* root = new Node();
        for (int i = 0; i < patternCnt; i++) {
            cin >> patterns[i];
            Node* cur = root;
            for (char c : patterns[i]) {
                int pos = (unsigned char)c;
                if (!cur->next[pos]) cur->next[pos] = new Node();
                cur = cur->next[pos];
            }
            cur->idx = i;
        }
        // 构建fail指针
        queue<Node*> q;
        root->fail = root;
        for (int i = 0; i < MAXN; i++) {
            if (root->next[i]) {
                root->next[i]->fail = root;
                q.push(root->next[i]);
            } else {
                root->next[i] = root;
            }
        }
        while (!q.empty()) {
            Node* cur = q.front();
            q.pop();
            for (int i = 0; i < MAXN; i++) {
                if (cur->next[i]) {
                    cur->next[i]->fail = cur->fail->next[i];
                    q.push(cur->next[i]);
                } else {
                    cur->next[i] = cur->fail->next[i];
                }
            }
        }
        // 单次遍历主串完成所有匹配
        Node* cur = root;
        for (char c : s) {
            int pos = (unsigned char)c;
            cur = cur->next[pos];
            for (Node* tmp = cur; tmp != root; tmp = tmp->fail) {
                if (tmp->idx != -1) exist[tmp->idx] = true;
            }
        }
        // 按顺序输出结果
        for (bool flag : exist) {
            ss << (flag ? 'y' : 'n') << '\n';
        }
    }
    cout << ss.str();
    return 0;
}

补充优化提示 #

如果测试用例中存在大量重复的模式串，可以在建树前先对模式串做哈希去重，相同的模式串只处理一次，能进一步减少运算量。

内容的提问来源于stack exchange，提问作者newToProgramming