用C++写一个基于AC自动机的敏感词检测系统后端部分

以下是一个基于AC自动机的敏感词检测系统后端部分的C++代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 10005;
const int MAXM = 100005;

int trie[MAXN][26], fail[MAXN], cnt = 0; // trie树，fail指针，节点计数器
int end[MAXN]; // 记录trie树上的单词节点
bool vis[MAXN]; // 记录访问过的节点
int n; // 敏感词的个数
char word[MAXM]; // 待检测的字符串
vector<int> sensitive; // 记录敏感词的出现位置

void insert(char *s, int id) // 插入单词
{
    int p = 0;
    for (int i = 0; s[i]; i++)
    {
        int c = s[i] - 'a';
        if (!trie[p][c])
            trie[p][c] = ++cnt;
        p = trie[p][c];
    }
    end[p] = id;
}

void buildAC() // 构建AC自动机
{
    queue<int> que;
    for (int i = 0; i < 26; i++)
        if (trie[0][i])
            que.push(trie[0][i]);
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = 0; i < 26; i++)
        {
            int &v = trie[u][i];
            if (v)
            {
                fail[v] = trie[fail[u]][i];
                que.push(v);
            }
            else
                v = trie[fail[u]][i];
        }
    }
}

void query() // 查询字符串中的敏感词
{
    int p = 0;
    for (int i = 0; word[i]; i++)
    {
        int c = word[i] - 'a';
        p = trie[p][c];
        for (int j = p; j && !vis[j]; j = fail[j])
        {
            vis[j] = true;
            if (end[j])
                sensitive.push_back(i - strlen(word) + 1); // 记录敏感词的出现位置
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        char s[MAXM];
        cin >> s;
        insert(s, i);
    }
    buildAC();
    cin >> word;
    query();
    if (sensitive.empty())
        cout << "No sensitive words found." << endl;
    else
    {
        for (int i = 0; i < sensitive.size(); i++)
        {
            for (int j = sensitive[i]; j < sensitive[i] + strlen(word); j++)
                cout << word[j];
            cout << " is a sensitive word at position " << sensitive[i] << "." << endl;
        }
    }
    return 0;
}

在该程序中，我们先使用`insert()`函数构建了一颗Trie树，并在每个单词的最后一个字母节点上标记该单词的编号，以便查询时能够输出敏感词的编号。接着，我们使用`buildAC()`函数构建了AC自动机，并在自动机上使用BFS算法将每个节点的fail指针指向其失败路径上的最长可匹配后缀节点。最后，我们使用`query()`函数在自动机上查询待检测的字符串，记录每个匹配到的单词节点，并输出其在字符串中的位置。