Pagini recente » Cod sursa (job #2853737) | Cod sursa (job #80234) | Cod sursa (job #874431) | Cod sursa (job #1705310) | Cod sursa (job #188242)
Cod sursa(job #188242)
#include <iostream>
#include <fstream>
using namespace std;
/*
* Un trie,
* Dar nu ca altii,
* Intr-un vector salvat,
* Punctaj mare de luat.
*/
char s[10000001];
int L;
char w[50000][21];
int lw[50000], N;
int trie[1100000][3];
bool final[1100000];
int main(int argc, char *argv[])
{
FILE *fi = fopen("abc2.in", "r");
fscanf(fi, "%s", s);
L = strlen(s);
for (N = 0; ; ++N) {
fscanf(fi, "%s", w[N]);
if (!w[N][0])
break;
lw[N] = strlen(w[N]);
}
fclose(fi);
int root = 1,
nstates = 1;
int state;
for (int cuv(0); cuv < N; ++cuv) {
state = root;
for (int i(0); i < lw[cuv]; ++i) {
if (final[state])
break;
w[cuv][i] -= 'a';
if (!trie[state][(int)w[cuv][i]]) {
++nstates;
trie[state][(int)w[cuv][i]] = nstates;
}
state = trie[state][(int)w[cuv][i]];
}
final[state] = true;
for (int i(0); i < 3; ++i)
trie[state][i] = 0;
/*for (int i(0); i < lw[cuv]; ++i)
cout << (char)(w[cuv][i] + 'a') << "\t";
cout << endl;
for (int i(0); i < nstates; ++i)
cout << final[i] << "\t";
cout << endl << endl;
for (int i(0); i < 3; ++i) {
for (int j(0); j < nstates; ++j)
cout << trie[j][i] << "\t";
cout << endl;
}
cout << endl;
cout << "---" << endl;*/
}
int lc = lw[0];
for (int i(0); i < L; ++i)
s[i] -= 'a';
int R(0);
for (int i(0); i < L - lc + 1; ++i) {
state = root;
int j = i;
while ((state > 0) && !final[state]) {
state = trie[state][(int)s[j]];
++j;
}
if (final[state])
++R;
}
ofstream fout("abc2.out");
fout << R << endl;
fout.close();
return 0;
}