Pagini recente » Cod sursa (job #386893) | Cod sursa (job #2011003) | Cod sursa (job #2281385) | Cod sursa (job #1390280) | Cod sursa (job #188731)
Cod sursa(job #188731)
#include <iostream>
#include <fstream>
using namespace std;
/*
* Cica pointeri sunt inceti,
* Cica malloc mananca timp,
* Cica, cica, cine stie?
*
* Un trie, dar c-un smen,
* E scris in vector,
* Unul mare. Ia trie[i][0]
* Pentru primul fiu, trie[i][1]
* Pentru al doilea iar trie[i][2]
* Pentru celalalt.
*
* Si ce-i un cuvant?
* O stare pentru care
* Isword de stare este true
*
* _ ///
* \ /_\ |
* )---|0|---| <--- un samurai
* / |_| ^
* _/ \_
*/
char text[10000001];
char cuv[21];
int trie[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++;
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';
if (!trie[state][next])
break;
state = trie[state][next];
if (isword[state])
++R;
}
}
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);
for (char *c = text; *c; ++c)
walk_trie(c);
ofstream fout("abc2.out");
fout << R << endl;
fout.close();
return 0;
}