Pagini recente » Cod sursa (job #1695064) | Cod sursa (job #2952663) | Cod sursa (job #480389) | Cod sursa (job #3318496) | Cod sursa (job #3307379)
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream cin("ahocorasick.in");
ofstream cout("ahocorasick.out");
/*
mici modificari ca sa verific daca e codul mai rapid
*/
const int NMAX = 1e6 + 5;
struct Node {
int kids[26];
int suffixLink;
int cnt;
void init() {
for (int i = 0; i < /*alphaSize*/26; i++) {
kids[i] = -1;
}
suffixLink = -1;
cnt = 0;
}
} nodes[NMAX];
int q[NMAX], qsize;
class AhoCorasick {
public:
int root;
int alphaSize;
int nrNodes;
AhoCorasick(int size) {
nrNodes = 0;
alphaSize = size;
root = ++nrNodes;
nodes[root].init();
}
int insert(string s) {
int node = root;
for (char ch: s) {
int childId = int(ch - 'a');
if (nodes[node].kids[childId] == -1) {
nodes[node].kids[childId] = ++nrNodes;
nodes[nrNodes].init();
}
node = nodes[node].kids[childId];
}
return node;
}
void solvePrefix(int node, int childId) {
int pref = nodes[node].suffixLink;
while (pref != root && nodes[pref].kids[childId] == -1) {
pref = nodes[pref].suffixLink;
}
if (nodes[pref].kids[childId] != -1 && nodes[pref].kids[childId] != nodes[node].kids[childId]) {
nodes[nodes[node].kids[childId]].suffixLink = nodes[pref].kids[childId];
} else {
nodes[nodes[node].kids[childId]].suffixLink = root;
}
}
void buildAndSolve(string s) {
nodes[root].suffixLink = root;
q[qsize++] = root;
for (int j = 0; j < qsize; j++) {
int node = q[j];
for (int i = 0; i < alphaSize; i++) {
if (nodes[node].kids[i] != -1) {
solvePrefix(node, i);
q[qsize++] = nodes[node].kids[i];
}
}
}
int node = root;
for (char ch: s) {
int childId = int(ch - 'a');
while (node != root && nodes[node].kids[childId] == -1) {
node = nodes[node].suffixLink;
}
if (nodes[node].kids[childId] != -1) {
node = nodes[node].kids[childId];
}
nodes[node].cnt++;
}
for (int i = qsize - 1; i >= 0; i--) {
nodes[nodes[q[i]].suffixLink].cnt += nodes[q[i]].cnt;
}
}
};
int main() {
int n;
string text;
cin >> text >> n;
AhoCorasick automaton(26);
int termNodes[n];
for (int i = 0; i < n; i++) {
string pattern;
cin >> pattern;
termNodes[i] = automaton.insert(pattern);
}
automaton.buildAndSolve(text);
for (int i = 0; i < n; i++) {
cout << nodes[termNodes[i]].cnt << '\n';
}
}