带有优先级字符串匹配问题

带有优先级的字符串匹配问题是指在匹配过程中，每个字符会有一个对应的优先级，高优先级的字符优先匹配。一种经典的解决方案是使用AC自动机算法。

AC自动机是一种高效的多模式匹配算法，它可以同时匹配多个模式串，并且具有线性时间复杂度。在AC自动机中，每个节点代表一个字符串前缀，节点之间的边表示字符的转移关系，边上的字符表示字符的匹配条件，每个节点还有一个fail指针，指向它的最长后缀节点，用于实现跳转到下一个匹配位置。

在实现带有优先级的字符串匹配时，可以在AC自动机的节点中加入优先级信息，并在匹配过程中考虑优先级的影响。具体来说，可以在AC自动机的每个节点中维护一个优先级队列，用于存储该节点对应的字符串的所有优先级，匹配时选择优先级最高的字符进行匹配。

下面是一个示例代码，实现了一个带有优先级的AC自动机：

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

struct Node {
    int fail; // fail指针
    vector<int> next; // 转移边
    priority_queue<char> pq; // 优先级队列
    Node() {
        fail = -1;
        next.resize(26, -1);
    }
};

vector<Node> buildAC(vector<string>& patterns) {
    vector<Node> ac(1);
    for (auto& p : patterns) {
        int u = 0;
        for (auto c : p) {
            if (ac[u].next[c - 'a'] == -1) {
                ac[u].next[c - 'a'] = ac.size();
                ac.emplace_back();
            }
            u = ac[u].next[c - 'a'];
            ac[u].pq.push(c);
        }
    }
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (ac[0].next[i] == -1) {
            ac[0].next[i] = 0;
        } else {
            q.push(ac[0].next[i]);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            int& v = ac[u].next[i];
            if (v == -1) {
                v = ac[ac[u].fail].next[i];
            } else {
                ac[v].fail = ac[ac[u].fail].next[i];
                q.push(v);
                while (!ac[ac[v].fail].pq.empty()) {
                    ac[v].pq.push(ac[ac[v].fail].pq.top());
                    ac[ac[v].fail].pq.pop();
                }
            }
        }
    }
    return ac;
}

void match(string s, vector<Node>& ac) {
    int u = 0;
    for (int i = 0; i < s.length(); i++) {
        while (!ac[u].pq.empty() && ac[u].pq.top() > s[i]) {
            ac[u].pq.pop();
        }
        u = ac[u].next[s[i] - 'a'];
        if (!ac[u].pq.empty()) {
            cout << "Matched pattern with highest priority " << ac[u].pq.top() << " at position " << i - ac[u].pq.size() + 1 << endl;
        }
    }
}

int main() {
    vector<string> patterns = {"abc", "bcd", "ab", "bcd", "d", "abcde"};
    vector<Node> ac = buildAC(patterns);
    string s = "abcdbcdabcde";
    match(s, ac);
    return 0;
}

在该示例代码中，我们首先定义了一个Node结构体，用于表示AC自动机的节点。其中，pq是一个优先级队列，用于存储该节点对应的字符串的所有优先级。在buildAC函数中，我们首先创建了一个空的AC自动机，然后对于每个模式串，逐个字符插入，并将该节点对应的优先级加入优先级队列。接着，我们使用BFS算法构建AC自动机，并在构建过程中维护优先级队列。在match函数中，我们首先遍历到一个新字符时，将当前节点的优先级队列中所有优先级大于该字符的字符弹出。之后，我们跳转到下一个节点，并检查该节点的优先级队列是否非空，如果非空，则说明匹配到了一个模式串，输出匹配信息。

需要注意的是，该示例代码仅作为演示AC自动机解决带有优先级的字符串匹配问题的一种方法，实际应用中需要根据具体情况进行实现。