Pagini recente » Cod sursa (job #2564658) | Cod sursa (job #1438625) | Cod sursa (job #1669175) | Cod sursa (job #2742296) | Cod sursa (job #1667129)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");
const int TEXT_LEN = 1000005;
const int WORD_LEN = 10005;
const int WCOUNT = 105;
struct trieNode
{
int pathCount;
int wIndex;
trieNode *s[26];
trieNode *failLink, *outLink;
trieNode()
{
wIndex = 0;
pathCount = 0;
memset(s, 0, sizeof(s));
failLink = outLink = 0;
}
};
char text[TEXT_LEN];
char word[WORD_LEN];
trieNode *root = new trieNode();
vector<trieNode*> bfsList;
queue<trieNode*> q;
int matchCount[WCOUNT];
void addWord(char *str, int index)
{
trieNode *t = root;
for(int i = 0; str[i] != 0; i++)
{
int cur_char = str[i] - 'a';
if(t->s[cur_char] == 0)
{
t->s[cur_char] = new trieNode();
}
t = t->s[cur_char];
}
t->wIndex = index;
}
void failLinkBfs()
{
root->failLink = root->outLink = root;
for(int i = 0; i < 26; i++)
{
if(root->s[i] != 0)
{
root->s[i]->failLink = root->s[i]->outLink = root;
q.push(root->s[i]);
}
}
while(!q.empty())
{
trieNode *cur = q.front();
bfsList.push_back(cur);
q.pop();
for(int i = 0; i < 26; i++)
{
trieNode *fl = cur->failLink;
if(cur->s[i] != 0)
{
trieNode *son = cur->s[i];
while(fl != root && fl->s[i] == 0)
{
fl = fl->failLink;
}
if(fl->s[i] != 0) fl = fl->s[i];
son->failLink = fl;
if(son->failLink->wIndex) son->outLink = son->failLink;
else son->outLink = son->failLink->outLink;
q.push(cur->s[i]);
}
}
}
}
void findMatches()
{
trieNode *t = root;
for(int i = 0; text[i] != 0; i++)
{
int cur_char = text[i] - 'a';
while(t != root && t->s[cur_char] == 0) t = t->failLink;
if(t->s[cur_char] != 0) t = t->s[cur_char];
t->pathCount++;
}
}
void dumpPaths()
{
reverse(begin(bfsList), end(bfsList));
for(auto t : bfsList)
{
t->outLink->pathCount += t->pathCount;
}
}
void ahoCorasick()
{
failLinkBfs();
findMatches();
dumpPaths();
for(auto t : bfsList)
{
if(t->wIndex)
{
matchCount[t->wIndex] = t->pathCount;
}
}
}
int main()
{
int n, i;
in >> text >> n;
for(i = 1; i <= n; i++)
{
in >> word;
addWord(word, i);
}
ahoCorasick();
for(i = 1; i <= n; i++)
{
out << matchCount[i] << '\n';
}
return 0;
}