Pagini recente » Cod sursa (job #2939399) | Cod sursa (job #663593) | Cod sursa (job #1604194) | Cod sursa (job #846260) | Cod sursa (job #3226108)
// Incercare fara pointeri.
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#define DL 1000005
#define DN 10005
#define DA 26 // dimensiunea alfabetului
using namespace std;
int lg, n, final[DN];
char tx[DL], c[DN];
struct ac {
vector<int> nd; // sirurile care se termina in nodul curent
int n0; // numarul de potriviri din nodul curent sau din fii lui
int f[DA], fail;
ac() : n0(0), fail(0) {
memset(f, -1, sizeof(f));
}
};
vector<ac> trie(1);
void ins(int t, char *p, int i) {
if (!isalpha(*p)) {
trie[t].nd.push_back(i);
return;
}
int urm = *p - 'a';
if (trie[t].f[urm] == -1) {
trie[t].f[urm] = trie.size();
trie.emplace_back();
}
ins(trie[t].f[urm], p + 1, i);
}
void bfs() {
vector<int> q;
q.push_back(0); // începem de la rădăcină
trie[0].fail = 0; // fail-ul rădăcinii este ea însăși
int front = 0;
while (front < q.size()) {
int fr = q[front++];
for (int i = 0; i < DA; ++i) {
if (trie[fr].f[i] != -1) {
int child = trie[fr].f[i];
int fail = trie[fr].fail;
while (fail != 0 && trie[fail].f[i] == -1)
fail = trie[fail].fail;
if (trie[fail].f[i] != -1)
fail = trie[fail].f[i];
trie[child].fail = fail;
q.push_back(child);
}
}
}
}
void process_text() {
int p = 0;
lg = strlen(tx);
for (int i = 0; i < lg; ++i) {
int urm = tx[i] - 'a';
while (trie[p].f[urm] == -1 && p != 0)
p = trie[p].fail;
if (trie[p].f[urm] != -1)
p = trie[p].f[urm];
trie[p].n0++;
}
}
void antibfs() {
vector<int> q;
for (int i = 0; i < trie.size(); ++i)
q.push_back(i);
for (int i = q.size() - 1; i >= 0; --i) {
int fr = q[i];
int fail = trie[fr].fail;
trie[fail].n0 += trie[fr].n0;
for (int idx : trie[fr].nd)
final[idx] = trie[fr].n0;
}
}
int main() {
freopen("ahocorasick.in", "r", stdin);
freopen("ahocorasick.out", "w", stdout);
scanf("%s", tx);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%s", c);
ins(0, c, i);
}
bfs();
process_text();
antibfs();
for (int i = 1; i <= n; ++i) printf("%d\n", final[i]);
return 0;
}