Pagini recente » Cod sursa (job #2507880) | Cod sursa (job #1600184) | Cod sursa (job #2718908) | Cod sursa (job #1407646) | Cod sursa (job #923508)
Cod sursa(job #923508)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int dimsir = 1000005, dimcuv = 10005, nrcuvmax = 105;
int N, NR[nrcuvmax];
char A[dimsir], C[nrcuvmax][dimcuv], *PC;
struct nod {
nod *letter[26], *suffix;
vector <int> index;
int value;
nod () {
value = 0;
suffix = NULL;
//for (int i = 0; i < 26; i++) letter[i] = NULL;
memset (letter, NULL, sizeof(letter));
}
} *R;
vector < nod* > Q;
void insert_trie (nod *&n, int i)
{
if (*PC == '\n' || *PC == 0)
{
n->index.push_back (i);
return;
}
char c = *PC - 'a';
if (n->letter[c] == NULL)
{
n->letter[c] = new nod;
}
PC ++;
insert_trie (n->letter[c], i);
}
void cit ()
{
R = new nod;
scanf ("%s\n%d\n", A, &N);
for (int i = 1; i <= N; i++)
{
scanf ("%s", C[i]);
PC = C[i];
insert_trie (R, i);
}
}
void bfs1 ()
{
int i, p = 0;
nod *n, *suffix;
for (i = 0; i < 26; i++)
{
if (R->letter[i] != NULL)
{
Q.push_back (R->letter[i]);
R->letter[i]->suffix = R;
}
}
R->suffix = R;
while (p < Q.size ())
{
n = Q[p];
for (i = 0; i < 26; i++)
if (n->letter[i] != NULL)
{
Q.push_back (n->letter[i]);
for (suffix = n->suffix; suffix != R && suffix->letter[i] == NULL; suffix = suffix->suffix);
if (suffix->letter[i] != NULL)
n->letter[i]->suffix = suffix->letter[i];
else
n->letter[i]->suffix = R;
}
p++;
}
}
void rez ()
{
nod *n = R; char c;
for (int i = 0; A[i] && A[i] != '\n'; i++)
{
for (c = A[i] - 'a'; n != R && n->letter[c] == NULL; n = n->suffix);
if (n->letter[c] != NULL) n = n->letter[c];
n->value ++;
}
}
void bfs2 ()
{
nod *n;
while (!Q.empty())
{
n = Q.back ();
Q.pop_back ();
n->suffix->value += n->value;
while (!n->index.empty())
{
NR[n->index.back()] = n->value;
n->index.pop_back ();
}
delete n;
}
}
void afi ()
{
for (int i = 1; i <= N; i++)
printf ("%d\n", NR[i]);
}
int main ()
{
freopen ("ahocorasick.in", "r", stdin);
freopen ("ahocorasick.out", "w", stdout);
cit ();
bfs1 ();
rez ();
bfs2 ();
afi ();
return 0;
}