Pagini recente » Cod sursa (job #1376700) | Cod sursa (job #1149707) | Cod sursa (job #1264283) | Cod sursa (job #1317776) | Cod sursa (job #189155)
Cod sursa(job #189155)
#include <iostream>
#include <fstream>
using namespace std;
/*
* Asta-i cica Corasick-Aho,
* Si-o suta ar-trebui sa ia.
*
* Foloseste un trie optimizat,
* Care nu-i altul decat Knuth-Morris-Pratt,
* In n patrat.
*/
char text[10000001];
char cuv[21];
int trie[1000001][3];
int nextn[1000001][3];
bool isword[1000001];
int N = 2;
int R = 0;
void insert_into_trie(char *cuv)
{
int state = 1;
int next;
for (char *c = cuv; *c; ++c) {
next = *c - 'a';
if (!trie[state][next])
trie[state][next] = N++;
nextn[state][next] = trie[state][next];
state = trie[state][next];
}
isword[state] = true;
}
void walk_trie(char *text)
{
int state = 1;
int next;
for (char *c = text; *c; ++c) {
next = *c - 'a';
state = nextn[state][next];
if (isword[state])
++R;
}
}
void build_nextn(int state, int *cand, int ncand)
{
/* cout << "Sunt la " << state << endl;
for (int i(0); i < ncand; ++i)
cout << cand[i] << " ";
cout << endl; */
for (int i(0); i < 3; ++i)
if (!nextn[state][i]) {
int nextstate = 1;
for (int j(0); j < ncand; ++j)
if (trie[cand[j]][i]) {
nextstate = trie[cand[j]][i];
break;
}
nextn[state][i] = nextstate;
}
int *newcand = new int[ncand+1];
int newncand = 0;
for (int i(0); i < 3; ++i)
if (trie[state][i]) {
newncand = 0;
for (int j(0); j < ncand; ++j)
if (trie[cand[j]][i])
newcand[newncand++] = trie[cand[j]][i];
newcand[newncand++] = 1;
build_nextn(trie[state][i], newcand, newncand);
}
delete newcand;
}
int main(int argc, char *argv[])
{
FILE *fi = fopen("abc2.in", "r");
fscanf(fi, "%s\n", text);
while (true) {
cuv[0] = 0;
fscanf(fi, "%s\n", cuv);
if (!cuv[0])
break;
insert_into_trie(cuv);
}
fclose(fi);
build_nextn(1, 0, 0);
walk_trie(text);
ofstream fout("abc2.out");
fout << R << endl;
fout.close();
return 0;
}