Pagini recente » Cod sursa (job #51913) | Cod sursa (job #635252) | Cod sursa (job #1656610) | Cod sursa (job #1404161) | Cod sursa (job #1508986)
#include <fstream>
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
struct Nod {
int bad, parent, cnt, leg[27];
};
Nod T[1000005];
int nodes, root;
int Where[105];
vector<int> G[1000005];
int Count[1000005];
void dfs(int node) {
for(auto vec : G[node]) {
dfs(vec);
Count[node] += Count[vec];
}
}
void addWord(char str[], int ind) {
int node = root;
for(int i=0; str[i]; i++) {
int &nw = T[node].leg[str[i]-'a'];
if(nw == 0) nw = ++nodes;
node = nw;
}
Where[ind] = node;
}
void make_links(int node, char pc, int parent) {
if(node == root) {
T[node].bad = -1;
} else {
int bad = T[parent].bad;
while(bad != -1 && !T[bad].leg[pc])
bad = T[bad].bad;
T[node].bad = (bad == -1) ? root : T[bad].leg[pc];
G[T[node].bad].push_back(node);
}
for(char c='a'-'a'; c<='z'-'a'; c++)
if(T[node].leg[c])
make_links(T[node].leg[c], c, node);
}
void go(char Text[]) {
int node = root;
for(int i=0; Text[i]; i++) {
while(node != -1 && !T[node].leg[Text[i]-'a'])
node = T[node].bad;
if(node != -1) {
node = T[node].leg[Text[i]-'a'];
Count[node] ++;
} else {
node = root;
}
}
}
char str[50000], se = 0;
void dump(int node) {
cerr<<node<<"("<<str<<"): ";
cerr<<"bad: "<<T[node].bad;
cout<<'\n';
for(char c='a'; c<='z'; c++) {
if(T[node].leg[c-'a']) {
str[se++] = c;
dump(T[node].leg[c-'a']);
str[--se] = 0;
}
}
}
char Text[1000005], Pattern[50005];
int main() {
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n;
fin>>Text>>n;
for(int i=1; i<=n; i++) {
fin>>Pattern;
addWord(Pattern, i);
}
make_links(root, 0, 0);
go(Text); dfs(root);
//dump(root);
for(int i=1; i<=n; i++) {
fout<<Count[Where[i]]<<'\n';
}
return 0;
}