Pagini recente » Cod sursa (job #1655538) | Cod sursa (job #2576306) | Cod sursa (job #552700) | Cod sursa (job #2387986) | Cod sursa (job #1842709)
#include <fstream>
#include <vector>
#include <string.h>
#include <queue>
#define sigma 26
#define PLen 10001
#define SLen 1000001
#define NWMax 101
using namespace std;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
int n, answ[NWMax];
char input[SLen], pattern[NWMax][PLen];
struct LinkedListElem {
int word;
LinkedListElem* next;
LinkedListElem(int _word) {
word = _word;
next = NULL;
}
};
struct Node {
Node* go[sigma];
Node* fail;
LinkedListElem* firstWord;
LinkedListElem* crtWord;
Node() {
memset(go, 0, sizeof go);
fail = NULL;
firstWord = NULL;
crtWord = NULL;
}
};
queue<Node*> QU;
Node* root;
void insert(Node* node, char* crtChar, int patCnt)
{
if (*crtChar == '\0') {
if (node->firstWord == NULL) {
node->firstWord = new LinkedListElem(patCnt);
node->crtWord = node->firstWord;
}
else {
node->crtWord->next = new LinkedListElem(patCnt);
node->crtWord = node->crtWord->next;
}
return;
}
char next = *crtChar - 'a';
if (node->go[next] == NULL)
node->go[next] = new Node();
insert(node->go[next], crtChar + 1, patCnt);
}
void compute_fail()
{
QU.push(root);
while (!QU.empty()) {
Node* crtNode = QU.front();
QU.pop();
for (int crtChar = 0; crtChar < sigma; crtChar++) {
Node* son = crtNode->go[crtChar];
if (son != NULL) {
QU.push(son);
Node* tmp = crtNode->fail;
while (tmp != NULL && tmp->go[crtChar] == NULL)
tmp = tmp->fail;
if (tmp == NULL)
son->fail = root;
else {
son->fail = tmp->go[crtChar];
if (son->firstWord != NULL)
son->crtWord->next = tmp->go[crtChar]->firstWord;
else
son->firstWord = son->crtWord = tmp->go[crtChar]->firstWord;
}
}
}
}
}
int main()
{
f >> input;
//root = createNode; ???
root = new Node();
f >> n;
for (int i = 1; i <= n; i++) {
f >> pattern[i];
insert(root, pattern[i], i);
}
compute_fail();
int len = strlen(input);
Node* tmp = root;
for (int pos = 0; pos < len; pos++) {
while (tmp != NULL && tmp->go[input[pos] - 'a'] == NULL)
tmp = tmp->fail;
if (tmp == NULL)
tmp = root;
tmp = tmp->go[input[pos] - 'a'];
if (tmp != NULL)
for (LinkedListElem* el = tmp->firstWord; el != NULL; el = el->next) {
//g << "Word " << pattern[el->word] << " occured at position " << pos - strlen(pattern[el->word]) + 1 << "\n";
answ[el->word]++;
}
}
for (int i = 1; i <= n; i++)
g << answ[i] << "\n";
return 0;
}