首页 > 其他 > 详细

AC自动机 P3808

时间:2020-10-02 00:21:12      阅读:1      评论:0      收藏:0      [点我收藏+]

标签:%s   get   pac   color   void   code   

前置知识:

1.KMP

2.Trie

 

其实我就是来贴个代码的好吧。

代码主要内容:

1.建Trie树

2.Getfail(得到fail值)

3.query

 

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e7 + 5;
 4 int n;
 5 char s[N];
 6 int Trie[N][27], val[N], fail[N];
 7 int cnt = 0;
 8 
 9 void build(void)
10 {
11     int len = strlen(s);
12     int now = 0;
13     for (int i = 0; i < len; i++)
14     {
15         if (!Trie[now][s[i] - a])
16         {
17             Trie[now][s[i] - a] = ++cnt;
18         }
19         now = Trie[now][s[i] - a];
20     }
21     val[now]++;
22     return;
23 }
24 
25 void Getfail(void)
26 {
27     queue<int> q;
28     for (int i = 0; i < 26; i++)
29     {
30         if (Trie[0][i])
31         {
32             fail[Trie[0][i]] = 0;
33             q.push(Trie[0][i]);
34         }
35     }
36     while (!q.empty())
37     {
38         int head = q.front();
39         q.pop();
40         for (int i = 0; i < 26; i++)
41         {
42             if (Trie[head][i])
43             {
44                 fail[Trie[head][i]] = Trie[fail[head]][i];
45                 q.push(Trie[head][i]);
46             }
47             else
48                 Trie[head][i] = Trie[fail[head]][i];
49         }
50     }
51     return;
52 }
53 
54 int query(void)
55 {
56     int len = strlen(s);
57     int now = 0, ans = 0;
58     for (int i = 0; i < len; i++)
59     {
60         now = Trie[now][s[i] - a];
61         for (int j = now; val[j] != -1; j = fail[j])
62             ans += val[j], val[j] = -1;
63     }
64     return ans;
65 }
66 
67 int main(void)
68 {
69     scanf("%d", &n);
70     for (int i = 1; i <= n; i++)
71     {
72         scanf("%s", s);
73         build();
74     }
75     Getfail();
76     scanf("%s", s);
77     printf("%d\n", query());
78     return 0;
79 }

 

 

AC自动机 P3808

标签:%s   get   pac   color   void   code   

原文:https://www.cnblogs.com/luyiming123blog/p/13758445.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号