Mai intai trebuie sa te autentifici.
Cod sursa(job #1736812)
Utilizator | Data | 2 august 2016 17:11:28 | |
---|---|---|---|
Problema | Aho-Corasick | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 2.95 kb |
#include <bits/stdc++.h>
using namespace std;
struct SuffixAutomaton {
struct Node {
int link, len;
map<char, int> leg;
};
vector<Node> T;
int last = 0, nodes = 1;
SuffixAutomaton(int sz) {
T.resize(sz);
T[0].link = -1;
T[0].len = 0;
occurences.resize(sz);
}
// Adds another character to the automaton
void ConsumeChar(char c) {
// Add state for whole string
int cur = nodes++;
T[cur].len = T[last].len + 1;
T[cur].link = 0;
int node = last;
// Add transitions to all suffixes which do not have one already
while(node != -1 && T[node].leg.count(c) == 0) {
T[node].leg[c] = cur;
node = T[node].link;
}
if(node != -1) {
// We found double-edge
int old = T[node].leg[c];
if(T[old].len == T[node].len + 1) {
// Just set a new link
T[cur].link = old;
} else {
// We have to split one edge
int clone = nodes++;
T[clone].leg = T[old].leg;
T[clone].len = T[node].len + 1;
T[clone].link = T[old].link;
// Set the "good" links
T[old].link = T[cur].link = clone;
// Rewire classes pointing to old
while(node != -1 && T[node].leg[c] == old) {
T[node].leg[c] = clone;
node = T[node].link;
}
}
}
last = cur;
occurences[cur] += 1;
}
vector<int> occurences;
void CountOccurences() {
queue<int> Q;
vector<int> degree(nodes);
for(int i = 1; i < nodes; ++i)
degree[T[i].link] += 1;
for(int i = 0; i < nodes; ++i)
if(degree[i] == 0) {
Q.push(i);
}
while(!Q.empty()) {
int i = Q.front();
Q.pop();
if(i == 0) continue;
occurences[T[i].link] += occurences[i];
if(--degree[T[i].link] == 0)
Q.push(T[i].link);
}
}
};
SuffixAutomaton automaton(200005);
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
string text, word;
cin >> text;
for(auto c : text)
automaton.ConsumeChar(c);
automaton.CountOccurences();
int n;
cin >> n;
while(n--) {
cin >> word;
int node = 0;
for(char c : word) {
if(automaton.T[node].leg.count(c) == 0) {
node = -1;
break;
}
node = automaton.T[node].leg[c];
}
if(node == -1) cout << "0\n";
else cout << automaton.occurences[node] << '\n';
}
return 0;
}