求给出的模式串中有多少个在文本串中出现过

    1. //trie的指针 
    2. int idx;
    3. struct node {
    4.     int fail;    //失配指针 
    5.     int ed;        //有多少单词以这个节点结尾 
    6.     int pos[30];//子节点的位置 
    7. }ac[N];
    9. //建trie树，向trie树中插入字符串s 
    10. void build(string s) {
    11.     int len = s.size();
    12.     int cur = 0;
    13.     for (int i = 0; i < len; i++) {
    14.         //若trie树中没有该节点，则构造出该节点 
    15.         if (!ac[cur].pos[s[i]-'a']) 
    16.             ac[cur].pos[s[i]-'a'] = ++idx;
    17.         //继续向下构造 
    18.         cur = ac[cur].pos[s[i]-'a'];
    19.     }
    20.     //标记单词结尾 
    21.     ac[cur].ed++; 
    23. }
    25. void get_fail() {
    26.     queue<int> q;
    27.     //提前处理第二层的fail指针 
    28.     for (int i = 0; i < 26; i++) {
    29.         if (ac[0].pos[i]) {
    30.             //指向根节点 
    31.             ac[ac[0].pos[i]].fail = 0;
    32.             q.push(ac[0].pos[i]);
    33.         }
    34.     }
    35.     //求fail指针 
    36.     while (q.size()) {
    37.         int u = q.front();
    38.         q.pop();
    39.         //枚举所有子节点 
    40.         for (int i = 0; i < 26; i++) {
    41.             //若子节点存在 
    42.             if (ac[u].pos[i]) {
    43.                 //子节点的fail指针指向当前节点的
    44.                 //fail指针所指向的节点的相同子节点 
    45.                 ac[ac[u].pos[i]].fail = ac[ac[u].fail].pos[i];
    46.                 q.push(ac[u].pos[i]);
    47.             //若子节点不存在 
    48.             } else {
    49.                 //当前节点的这个子节点指向当前
    50.                 //节点fail指针的这个子节点 
    51.                 ac[u].pos[i] = ac[ac[u].fail].pos[i];
    52.             } 
    53.         } 
    54.     }
    55. }
    57. int ac_query(string s) {
    58.     int len = s.size();
    59.     int cur = 0, res = 0;
    60.     for (int i = 0; i < len; i++) {
    61.         //继续下一层 
    62.         cur = ac[cur].pos[s[i]-'a'];
    63.         for (int j = cur; j&&ac[j].ed!=-1; j = ac[j].fail) {
    64.             res += ac[j].ed;
    65.             ac[j].ed = -1;
    66.         }
    67.     }
    68.     return res; 
    69. } 
    71. signed main() {
    72.     int n;
    73.     cin >> n;
    74.     string s;
    75.     for (int i = 1; i <= n; i++) {
    76.         cin >> s;
    77.         build(s);
    78.     }
    79.     ac[0].fail = 0;    //结束标志
    80.     get_fail();        //求失配指针
    81.     string txt;
    82.     cin >> txt;
    83.     cout << ac_query(txt) << "\n"; 
    84.     return 0;
    85. }