Pagini recente » Cod sursa (job #1123321) | Cod sursa (job #3122980) | Cod sursa (job #2782879) | Cod sursa (job #2680030) | Cod sursa (job #2312864)
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define zeros(x) x&(-x)
#define all(v) v.begin(), v.end()
#define MOD 104659
#define oo 2000000000
#define pii pair<int,int>
#define ll long long
#define ld long double
#define ull unsigned long long
#define mem(a) memset(a,0,sizeof(a))
#define pi 3.14159265359
#define NMax 60
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct trie
{
vector<int> words;
trie *next[27], *error;
int cnt;
trie ()
{
cnt = 0;
words.clear();
error = 0;
memset(next,0,sizeof(next));
}
};
trie *root = new trie();
int n, sol[105];
string a, s;
vector<trie *> ord;
void insert(string w, int idx)
{
trie *aux = root;
for (int i=0; i<w.length(); ++i)
{
if (aux->next[w[i]-'a']==0) aux->next[w[i]-'a']=new trie();
aux = aux->next[w[i]-'a'];
}
aux->words.push_back(idx);
}
void drumuri()
{
ord.clear();
ord.push_back(root);
for (int i=0; i<ord.size(); ++i)
for (int j=0; j<=26; ++j)
if (ord[i]->next[j]!=0)
{
ord.push_back(ord[i]->next[j]);
trie *start = ord[i]->error;
while (start!=root && start->next[j]==0) start = start->error;
if (ord[i]!=root && start->next[j]!=0) ord[i]->next[j]->error = start->next[j];
else ord[i]->next[j]->error = root;
}
}
void calc(trie *aux)
{
for (int i=ord.size()-1; i>=0; --i)
{
aux = ord[i];
aux->error->cnt += aux->cnt;
for (int j=0; j<aux->words.size(); ++j)
sol[aux->words[j]]=aux->cnt;
}
}
int main()
{
fin>>a;
fin>>n;
for (int i=1; i<=n; ++i)
{
fin>>s;
insert(s, i);
}
root->error = root;
drumuri();
trie *aux = root;
for (int i=0; i<a.length(); ++i)
{
while (aux->next[a[i]-'a'] ==0 && aux!=root) aux = aux->error;
if (aux->next[a[i]-'a'] !=0) aux = aux->next[a[i]-'a'];
++aux->cnt;
}
calc(root);
for (int i=1; i<=n; ++i) fout<<sol[i]<<"\n";
return 0;
}