咨询公司招聘_三星网上商城投诉电话_怎么做百度网页_windows优化大师官网

constexpr int N = 500010;
constexpr int ALPHABET = 26;
char convert = 'a';
class AhoCorasick {
private:int trie[N][ALPHABET];int fail[N];int tot = 1,Q=0;std::vector<int> nodes, f;
public:AhoCorasick(int _Q) :Q{ _Q }{for (int i = 0; i < ALPHABET; i++) {trie[0][i] = 1;}}int add(std::string& s) {int p = 1;for (auto c : s) {int& q = trie[p][c - convert];if (q == 0)q = ++tot;p = q;}return p;}void work() {std::queue<int> q;q.push(1);while (!q.empty()) {int x = q.front();nodes.push_back(x);q.pop();//对于每个节点,访问它的子节点for (int i = 0; i < ALPHABET; i++) {if (trie[x][i] == 0) {//如果子节点不存在trie[x][i] = trie[fail[x]][i];//将它的值设为失配指针指向节点的子节点//理由是失配指针每次指向的都是最长后缀的位置,所以如果能匹配到下一个字符是正确的}else {//如果节点存在fail[trie[x][i]] = trie[fail[x]][i];//该子节点失配指针等于父节点的失配指针所指向的子节点q.push(trie[x][i]);//并将它放入队列}}}}std::vector<int> search(std::string S) {f.resize(tot + 1);int p = 1;for (auto c : S) {//遍历每一个字符p = trie[p][c - convert];//根节点下如果有这个字符f[p]++;//让f[p]++;}//从最后一个访问的节点开始回溯for (int i = nodes.size() - 1; i >= 0; i--) {int x = nodes[i];//拿到该节点的序号f[fail[x]] += f[x];//如果x所代表的字符串出现过,代表其最长后缀也出现过//而x的最长后缀所指向的末尾字符就是fail指针所指向的末尾字符}return f;}
};int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int Q;std::cin >> Q;std::string s;std::vector<int>end(Q);AhoCorasick ac(Q);for (int i = 0; i < Q; i++) {std::cin >> s;end[i] = ac.add(s);}ac.work();std::cin >>s;std::vector<int>f = ac.search(s);for (int i = 0; i < Q; i++) {std::cout << f[end[i]] << "\n";}return 0;
}

使用方式,add会返回该字符串最后一个字符所处节点,需要创建一个end数组进行接受,add用于添加敏感词,ac.work用于构建失配指针,ac.search会返回一个数组f,f[end[i]]表示第i个字符出现的次数.