Pagini recente » Cod sursa (job #2315367) | Cod sursa (job #760009) | Cod sursa (job #1012565) | Cod sursa (job #493095) | Cod sursa (job #1844432)
#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], idx;
char input[SLen], pattern[NWMax][PLen];
bool mark[NWMax];
struct LinkedListElem {
int word;
LinkedListElem* next;
LinkedListElem(int _word) {
word = _word;
next = NULL;
}
};
struct Node {
Node* go[sigma];
Node* fail;
LinkedListElem* firstWord;
LinkedListElem* crtWord;
int count;
int label;
Node(int _idx) {
memset(go, 0, sizeof go);
fail = NULL;
firstWord = NULL;
crtWord = NULL;
label = _idx;
count = 0;
}
};
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(++idx);
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 = tmp->go[crtChar]->firstWord;
son->crtWord = tmp->go[crtChar]->crtWord;
}
}
}
}
}
}
void DFS(Node* node)
{
mark[node->label] = true;
for (LinkedListElem* crt = node->firstWord; crt != NULL; crt = crt->next)
answ[crt->word] += node->count;
for (int c = 0; c < 26; c++)
if (node->go[c] != NULL)
DFS(node->go[c]);
}
int main()
{
f >> input;
root = new Node(++idx);
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)
tmp->count++;
}
DFS(root);
for (int i = 1; i <= n; i++)
g << answ[i] << "\n";
return 0;
}