Pagini recente » Cod sursa (job #1879867) | Cod sursa (job #1057201) | Cod sursa (job #956833) | Cod sursa (job #1619698) | Cod sursa (job #188480)
Cod sursa(job #188480)
#include <iostream>
#include <fstream>
using namespace std;
const int TextLen = 10000000;
char text[TextLen+1];
char cuv[21];
int trie[1000001][3];
bool isword[1000001];
int N(2);
int numwords(0);
void insert_into_trie(char *cuv)
{
/*cout << "Inserting " << cuv << " into trie." << endl;*/
int state = 1;
int p;
for (char *c = cuv; *c && !isword[state]; ++c) {
p = *c - 'a';
if (!trie[state][p])
trie[state][p] = N++;
state = trie[state][p];
}
isword[state] = true;
/*cout << "State " << state << " is a word." << endl;*/
}
void walk_trie(char *t)
{
int state = 1;
int p;
for (char *c = t; *c; ++c) {
p = *c - 'a';
if (!trie[state][p])
break;
state = trie[state][p];
if (isword[state]) {
++numwords;
/*cout << "Found a word at state " << state << endl;*/
}
}
}
int main(int argc, char *argv[])
{
FILE *fi = fopen("abc2.in", "r");
fscanf(fi, "%s\n", text);
/*cout << text << endl;*/
while (true) {
cuv[0] = 0;
fscanf(fi, "%s\n", cuv);
if (!cuv[0])
break;
insert_into_trie(cuv);
/*for (int j(0); j < 3; ++j) {
for (int i(1); i < N; ++i)
cout << (int)trie[i][j] << " ";
cout << endl;
}
cout << endl;*/
}
fclose(fi);
for (char *c = text; *c; ++c)
walk_trie(c);
ofstream fout("abc2.out");
fout << numwords << endl;
fout.close();
return 0;
}