Pagini recente » Cod sursa (job #2588804) | Cod sursa (job #893447) | Cod sursa (job #37912) | Cod sursa (job #2519119) | Cod sursa (job #2245166)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define NMAX 101
#define ALPHA 26
struct Prefix {
int next[ALPHA];
int link, p;
char pch;
bool leaf;
int cnt;
vector <int> idx;
Prefix(int p = -1, char pch = '$') {
fill(begin(next), end(next), -1);
link = -1;
leaf = false;
cnt = 0;
this->p = p;
this->pch = pch;
}
};
vector <Prefix> v(1);
int sol[NMAX];
void add_string(const string& s, int idx) {
int q = 0;
for (const char& ch : s) {
int idx = ch - 'a';
if (v[q].next[idx] == -1) {
v[q].next[idx] = v.size();
v.emplace_back(q, ch);
}
q = v[q].next[idx];
}
v[q].leaf = true;
v[q].idx.push_back(idx);
}
int get_suffix(const int p) {
if (v[p].link != -1)
return v[p].link;
if (p == 0 || v[p].p == 0) {
v[p].link = 0;
return 0;
}
int plink = get_suffix(v[p].p);
while (plink) {
if (v[plink].next[v[p].pch - 'a'] != -1)
break;
plink = get_suffix(plink);
}
if (v[plink].next[v[p].pch - 'a'] != -1) {
v[p].link = v[plink].next[v[p].pch - 'a'];
} else {
v[p].link = 0;
}
return v[p].link;
}
void build_links() {
queue<int> q;
q.push(0);
while (!q.empty()) {
int node = q.front();
q.pop();
v[node].link = get_suffix(node);
for (int i = 0; i < ALPHA; i++) {
if (v[node].next[i] != -1)
q.push(v[node].next[i]);
}
}
}
int main () {
int n;
string a;
ifstream f("ahocorasick.in");
ofstream g("ahocorasick.out");
f >> a;
f >> n;
for (int i = 1; i <= n; i++) {
string b;
f >> b;
add_string(b, i);
}
f.close();
build_links();
int q = 0;
for (const char& ch : a) {
int idx = ch - 'a';
while (q) {
if (v[q].next[idx] != -1)
break;
q = v[q].link;
}
if (v[q].next[idx] != -1) {
q = v[q].next[idx];
}
if (q) {
v[q].cnt++;
}
}
vector <int> ord;
{
queue<int> q;
q.push(0);
while (!q.empty()) {
int node = q.front();
q.pop();
ord.push_back(node);
for (int i = 0; i < ALPHA; i++) {
if (v[node].next[i] != -1)
q.push(v[node].next[i]);
}
}
}
reverse(ord.begin(), ord.end());
for (const int node : ord) {
v[v[node].link].cnt += v[node].cnt;
}
for (const int node : ord) {
if (v[node].leaf) {
for (const int idx : v[node].idx)
sol[idx] = v[node].cnt;
}
}
for (int i = 1; i <= n; i++) {
g << sol[i] << '\n';
}
g.close();
return 0;
}