HDU 2896 바이러스 침입 (AC 자동 동기)
31302 단어 AC 자동 동기
제목: n 개의 패턴 문자열, m 개의 메 인 문자열 을 드 리 고 모든 메 인 문자열 에 나타 나 는 패턴 문자열 의 레이 블 을 구 합 니 다.
사고: AC 자동 동기 물 문제, trie 트 리 에서 레이 블 을 유지 하고 m 번 스 캔 하면 됩 니 다. 출력 형식 에 주의 하 십시오.
code：
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4 #include <set>
5 using namespace std;
6 const int MAXN = 10005;
7 const int KIND = 128;
8
9 struct node
10 {
11 int id;
12 node* fail;
13 node* next[KIND];
14 node()
15 {
16 id = 0;
17 fail = NULL;
18 for (int i = 0; i < KIND; ++i) next[i] = NULL;
19 }
20 };
21 node* root;
22 int L = 0;
23 char str[MAXN];
24 set<int> ans;
25
26 void Insert(char str[])
27 {
28 node* temp = root;
29 int len = strlen(str);
30 for (int i = 0; i < len; ++i)
31 {
32 if (temp->next[str[i]] == NULL)
33 temp->next[str[i]] = new node();
34 temp = temp->next[str[i]];
35 }
36 temp->id = ++L;
37 }
38
39 void Build()
40 {
41 queue<node*>Q;
42 root->fail = root;
43 for (int i = 0; i < KIND; ++i)
44 {
45 if (root->next[i] == NULL)
46 root->next[i] = root;
47 else
48 {
49 root->next[i]->fail = root;
50 Q.push(root->next[i]);
51 }
52 }
53 while (!Q.empty())
54 {
55 node* temp = Q.front();
56 Q.pop();
57 for (int i = 0; i < KIND; ++i)
58 {
59 if (temp->next[i] == NULL)
60 temp->next[i] = temp->fail->next[i];
61 else
62 {
63 temp->next[i]->fail = temp->fail->next[i];
64 Q.push(temp->next[i]);
65 }
66 }
67 }
68 }
69
70 int Query(char str[])
71 {
72 node* temp = root;
73 int len = strlen(str);
74 ans.clear();
75 for (int i = 0; i < len; ++i)
76 {
77 while (temp->next[str[i]] == NULL && temp != root) temp = temp->fail;
78 temp = temp->next[str[i]];
79 if (temp == NULL) temp = root;
80 node* x = temp;
81 while (x != root)
82 {
83 if (x->id != 0) ans.insert(x->id);
84 x = x->fail;
85 }
86 }
87 return ans.size();
88 }
89
90
91 int main()
92 {
93 int n, m;
94 int tot = 0;
95 while (scanf("%d", &n) != EOF)
96 {
97 root = new node();
98 for (int i = 0; i < n; ++i)
99 {
100 scanf("%s", str);
101 Insert(str);
102 }
103 Build();
104 scanf("%d", &m);
105 for (int i = 1; i <= m; ++i)
106 {
107 scanf("%s", str);
108 int num = Query(str);
109 if (num == 0) continue;
110 printf("web %d:", i);
111 set<int>::iterator it;
112 for (it = ans.begin(); it != ans.end(); ++it) printf(" %d", *it);
113 printf("
");
114 ++tot;
115 }
116 printf("total: %d
", tot);
117 }
118 return 0;
119 }배열 구현:
1 #include <cstdio>
2 #include <cstring>
3 #include <queue>
4 #include <set>
5 using namespace std;
6 const int KIND = 128;
7 const int MAXN = 100005;
8 const int MAXM = 10005;
9
10 struct Trie
11 {
12 int next[MAXN][KIND], fail[MAXN], id[MAXN];
13 int root, L, num;
14 set<int> ans;
15 int create()
16 {
17 for (int i = 0; i < KIND; ++i)
18 next[L][i] = -1;
19 id[L++] = 0;
20 return L - 1;
21 }
22 void init()
23 {
24 num = 0;
25 L = 0;
26 root = create();
27 }
28 void insert(char str[])
29 {
30 int now = root;
31 int len = strlen(str);
32 for (int i = 0; i < len; ++i)
33 {
34 if (-1 == next[now][str[i]])
35 next[now][str[i]] = create();
36 now = next[now][str[i]];
37 }
38 id[now] = ++num;
39 }
40 void build()
41 {
42 queue<int>Q;
43 fail[root] = root;
44 for (int i = 0; i < KIND; ++i)
45 {
46 if (-1 == next[root][i])
47 next[root][i] = root;
48 else
49 {
50 fail[next[root][i]] = root;
51 Q.push(next[root][i]);
52 }
53 }
54 while (!Q.empty())
55 {
56 int now = Q.front();
57 Q.pop();
58 for (int i = 0; i < KIND; ++i)
59 {
60 if (-1 == next[now][i])
61 next[now][i] = next[fail[now]][i];
62 else
63 {
64 fail[next[now][i]] = next[fail[now]][i];
65 Q.push(next[now][i]);
66 }
67 }
68 }
69 }
70 int query(char str[])
71 {
72 ans.clear();
73 int now = root;
74 int len = strlen(str);
75 for (int i = 0; i < len; ++i)
76 {
77 now = next[now][str[i]];
78 int temp = now;
79 while (temp != root)
80 {
81 if (id[temp]) ans.insert(id[temp]);
82 temp = fail[temp];
83 }
84 }
85 return (int)ans.size();
86 }
87 };
88 Trie ac;
89 char str[MAXM];
90 int main()
91 {
92 int n, m, tot;
93 while (scanf("%d", &n) != EOF)
94 {
95 ac.init();
96 tot = 0;
97 for (int i = 0; i < n; ++i)
98 {
99 scanf("%s", str);
100 ac.insert(str);
101 }
102 ac.build();
103 scanf("%d", &m);
104 for (int i = 1; i <= m; ++i)
105 {
106 scanf("%s", str);
107 if (0 == ac.query(str)) continue;
108 printf("web %d:", i);
109 set<int>::iterator it;
110 for (it = ac.ans.begin(); it != ac.ans.end(); ++it) printf(" %d", *it);
111 printf("
");
112 ++tot;
113 }
114 printf("total: %d
", tot);
115 }
116 return 0;
117 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[AC 자동 동기] hdoj 3065: 바이러스 침입 지속 중대체로 제목: n 개의 패턴 문자열, 하나의 텍스트 문자열 을 보 여 줍 니 다. 각각 텍스트 문자열 이 패턴 문자열 에 나타 나 는 횟수 를 구 합 니 다. 대체적인 사고방식: 기본 적 인 AC 자동 동 기 는 일...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
