Pagini recente » Cod sursa (job #1801720) | Cod sursa (job #2790763) | Cod sursa (job #196946) | Cod sursa (job #726839) | Cod sursa (job #1726767)
#include<fstream>
#include<string.h>
#include<queue>
using namespace std;
struct Node
{
Node* c[27];
vector<int> nr;
int sm;
Node *fail;
}*Trie;
int f[110];
char s[1000010];
char a[10010];
queue<Node*> Q;
vector<Node*> vec;
void init()
{
Trie = new Node;
memset(Trie, 0, sizeof(Node));
}
void add_to_trie(int nr,const char *s)
{
Node *node = Trie;
for (int i = 0;s[i] != '\0';++i)
{
if (node->c[s[i] - 'a'])
node = node->c[s[i] - 'a'];
else
{
node->c[s[i] - 'a'] = new Node;
memset(node->c[s[i] - 'a'], 0, sizeof(Node));
node = node->c[s[i] - 'a'];
}
}
node->nr.push_back(nr);
}
void create_fail_links()
{
Q.push(Trie);
while (Q.size())
{
Node *node = Q.front();
vec.push_back(node);
for (int i = 0;i < 27;++i)
{
if (!node->c[i])
continue;
Node *fail = node->fail;
while (fail)
{
if (fail->c[i])
{
node->c[i]->fail = fail->c[i];
break;
}
fail = fail->fail;
}
if (!fail && Trie->c[i] && Trie->c[i]!=node->c[i])
node->c[i]->fail = Trie->c[i];
else if(!fail)
node->c[i]->fail = Trie;
Q.push(node->c[i]);
}
Q.pop();
}
}
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
int main()
{
in >> s;
int N;
in >> N;
init();
for (int i = 1;i <= N;++i)
{
in >> a;
add_to_trie(i,a);
}
create_fail_links();
Node *node = Trie;
for (int i = 0;s[i] != '\0';++i)
{
while (node != Trie && !node->c[s[i] - 'a'])
node = node->fail;
if (node->c[s[i] - 'a'])
node = node->c[s[i] - 'a'];
node->sm += 1;
}
for (int i = vec.size() - 1;i >= 0;--i)
{
for (int j = 0;j < vec[i]->nr.size();++j)
f[vec[i]->nr[j]] = vec[i]->sm;
if(vec[i]->fail)
vec[i]->fail->sm += vec[i]->sm;
}
for (int i = 1;i <= N;++i)
out << f[i] << '\n';
return 0;
}