Pagini recente » Cod sursa (job #2590467) | Cod sursa (job #649819) | Cod sursa (job #2589098) | Cod sursa (job #2276134) | Cod sursa (job #3349096)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
int n,i,j,k,ans[105],cnt;
string s,a;
queue<int> q;
struct nod{
char c = '\0';
vector<int> children;
int fallback = 0;
vector<int> outputs;
int output = 0;
} trie[1000005];
void add(int x, int ind){
if(ind == a.size()){
trie[x].outputs.push_back(i);
trie[x].output = trie[x].outputs.size();
return;
}
for(auto it:trie[x].children){
if(trie[it].c == a[ind]){
add(it, ind+1);
return;
}
}
cnt++;
trie[x].children.push_back(cnt);
trie[cnt].c = a[ind];
add(trie[x].children.back(), ind+1);
}
int find_fallback(int x, char c){
x = trie[x].fallback;
for(auto it:trie[x].children){
if(trie[it].c == c)
return it;
}
if(x == 1)
return 1;
return find_fallback(x, c);
}
void build(){
trie[1].fallback = 1;
for(auto it:trie[1].children){
trie[it].fallback = 1;
q.push(it);
}
int x;
while(!q.empty()){
x = q.front();
q.pop();
for(auto it:trie[x].children){
trie[it].fallback = find_fallback(x, trie[it].c);
for(auto it2:trie[trie[it].fallback].outputs)
trie[it].outputs.push_back(it2);
q.push(it);
}
}
}
void parc(int x, int ind){
if(ind == s.size()){
for(auto it:trie[x].outputs)
ans[it]++;
return;
}
for(auto it:trie[x].children){
if(trie[it].c == s[ind]){
for(auto it:trie[x].outputs)
ans[it]++;
parc(it, ind+1);
return;
}
}
if(x == 1){
parc(1, ind+1);
return;
}
for(int i=0;i<trie[x].output;i++)
ans[trie[x].outputs[i]]++;
parc(trie[x].fallback, ind);
}
int main()
{
fin>>s;
fin>>n;
cnt = 1;
for(i=1;i<=n;i++){
fin>>a;
add(1, 0);
}
build();
parc(1,0);
for(i=1;i<=n;i++)
fout<<ans[i]<<'\n';
return 0;
}