Pagini recente » Cod sursa (job #1486428) | Cod sursa (job #450195) | Cod sursa (job #549627) | Cod sursa (job #2365048) | Cod sursa (job #1757483)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <map>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
const int dim = 1000005;
struct Node {
int len, link;
map< int, int > next;
Node() {
len = link = 0;
}
} nodes[2 * dim];
int sz, last;
void Init() {
sz = last = 0;
nodes[0].len = 0;
nodes[0].link = -1;
sz++;
}
set< pair<int, int> > base;
int cnt[2 * dim];
void Update(int letter) {
int curr = sz++;
nodes[curr].len = nodes[last].len + 1;
cnt[curr] = 1;
base.insert(make_pair(nodes[curr].len, curr));
int p;
for (p = last; p != -1 && !nodes[p].next.count(letter); p = nodes[p].link)
nodes[p].next[letter] = curr;
if (p == -1)
nodes[curr].link = 0;
else {
int q = nodes[p].next[letter];
if (nodes[p].len + 1 == nodes[q].len)
nodes[curr].link = q;
else {
int clone = sz++;
nodes[clone].len = nodes[p].len + 1;
nodes[clone].next = nodes[q].next;
nodes[clone].link = nodes[q].link;
cnt[clone] = 0;
base.insert(make_pair(nodes[clone].len, clone));
for (; p != -1 && nodes[p].next[letter] == q; p = nodes[p].link)
nodes[p].next[letter] = clone;
nodes[q].link = nodes[curr].link = clone;
}
}
last = curr;
}
void BuildCnt() {
for (set< pair<int, int> >::reverse_iterator it = base.rbegin(); it != base.rend(); ++it)
cnt[nodes[it->second].link] += cnt[it->second];
}
int CountOccurances(const string pattern) {
size_t pos = 0;
int curr = 0;
while (pos < pattern.length() && nodes[curr].next.count(pattern[pos] - 'a'))
curr = nodes[curr].next[pattern[pos] - 'a'], pos++;
return (curr == -1 ? 0 : cnt[curr]);
}
int main() {
string a;
fin >> a;
Init();
for (size_t i = 0; i < a.length(); ++i)
Update(a[i] - 'a');
BuildCnt();
int n; fin >> n;
while (n--) {
fin >> a;
fout << CountOccurances(a) << '\n';
}
return 0;
}
//Trust me, I'm the Doctor!