Pagini recente » Cod sursa (job #571788) | Cod sursa (job #2449907) | Cod sursa (job #1112107) | Cod sursa (job #1786) | Cod sursa (job #2231777)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");
class TRIE
{
public:
TRIE *suffix_Link;
TRIE *letter[26];
int apparitions;
TRIE()
{
for ( int i = 0; i <= 26; ++i )
letter[i] = nullptr;
suffix_Link = nullptr;
apparitions = 0;
}
};
int n;
TRIE *root;
TRIE *answer[105];
string s;
void insertWord( string word, int indx )
{
TRIE *current_Root = root;
for ( auto x : word )
{
int current_Position = x-'a';
if ( current_Root->letter[current_Position] == nullptr )
current_Root->letter[current_Position] = new TRIE();
current_Root = current_Root->letter[current_Position];
}
answer[indx] = current_Root;
}
queue <TRIE*> road;
stack <TRIE*> reversed_Road;
void buildSuffixLinks()
{
root->suffix_Link = root;
road.push(root);
while ( road.size() )
{
TRIE *current_Node = road.front();
reversed_Road.push(current_Node);
road.pop();
for ( int i = 0; i < 26; ++i )
{
if ( current_Node->letter[i] )
{
TRIE *current_Suffix = current_Node->suffix_Link;
while ( current_Suffix->letter[i] == nullptr && current_Suffix != root )
current_Suffix = current_Suffix->suffix_Link;
if ( current_Suffix->letter[i] != current_Node->letter[i] )
current_Node->letter[i]->suffix_Link = current_Suffix->letter[i];
else
current_Node->letter[i]->suffix_Link = root;
road.push(current_Node->letter[i]);
}
}
}
}
void getApparitions()
{
TRIE *current_Root = root;
for ( auto x:s )
{
int current_Position = x-'a';
while ( current_Root != root && current_Root->letter[current_Position] == nullptr )
current_Root = current_Root->suffix_Link;
if ( current_Root->letter[current_Position] )
current_Root = current_Root->letter[current_Position];
current_Root->apparitions++;
}
while ( reversed_Road.size() )
{
TRIE *current_Node = reversed_Road.top();
reversed_Road.pop();
current_Node->suffix_Link->apparitions += current_Node->apparitions;
}
}
int main()
{
ios::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
root = new TRIE();
fin>>s;
fin>>n;
for ( int i = 1; i <= n; ++i )
{
string word;
fin>>word;
insertWord(word, i);
}
buildSuffixLinks();
getApparitions();
for ( int i = 1; i <= n; ++i )
fout<<answer[i]->apparitions<<'\n';
}