Pagini recente » Cod sursa (job #1069155) | Cod sursa (job #2752396) | Cod sursa (job #51885) | Cod sursa (job #1108277) | Cod sursa (job #1667146)
#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];
int wordId[WCOUNT];
int 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];
}
if(!t->wIndex) {
t->wIndex = index;
}
return t->wIndex;
}
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;
wordId[i] = addWord(word, i);
}
ahoCorasick();
for(i = 1; i <= n; i++) {
out << matchCount[wordId[i]] << '\n';
}
return 0;
}