Pagini recente » Cod sursa (job #1904198) | Cod sursa (job #1564753) | Cod sursa (job #2645927) | Borderou de evaluare (job #3248889) | Cod sursa (job #101335)
Cod sursa(job #101335)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <set>
using namespace std;
string text;
unsigned long p[21];
// set<unsigned long> words;
class SearchTree {
public:
SearchTree() {
child[0] = child[1] = child[2] = 0;
val = 0;
cnt = 0;
}
void insert(unsigned long _val) {
if (_val == 0) {
++cnt;
return;
}
int c = _val % 3;
if (!child[c]) {
child[c] = new SearchTree;
child[c]->val = c;
}
child[c]->insert(_val / 3);
}
int count(unsigned long _val) {
if (_val == 0)
return cnt;
int c = _val % 3;
if (!child[c])
return 0;
return child[c]->count(_val / 3);
}
SearchTree *child[3];
int val;
int cnt;
};
SearchTree words;
int main(int argc, char *argv[]) {
ifstream fin("abc2.in");
fin >> text;
bool notCalculated(true);
int tot(0);
int n;
do {
string aux;
fin >> aux;
if (!aux.empty()) {
if (notCalculated) {
notCalculated = false;
n = aux.size();
p[0] = 1;
for (int i(1); i <= n; ++i)
p[i] = p[i - 1] * 3;
}
unsigned long c = 0;
for (int i(0); i < n; ++i)
c += (aux[i] - 'a') * p[i];
// cout << c << endl;
words.insert(c);
}
} while (!fin.eof());
fin.close();
unsigned long c = 0;
int i(0);
unsigned long p = 1;
for (; i < n; ++i) {
c += (text[i] - 'a') * p;
p *= 3;
}
p /= 3;
if (words.count(c))
++tot;
for (; i < (int)text.size(); ++i) {
c /= 3;
c += p * (text[i] - 'a');
if (words.count(c))
++tot;
}
// for (int i(0); i < (int)cs.size(); ++i)
// if (words.count(cs[i]))
// ++tot;
// for (int i(0); i < (int)cs.size(); ++i)
// if (c == cs[i]) {
// cs[i] = -1;
// ++tot;
// }
ofstream fout("abc2.out");
fout << tot << endl;
fout.close();
return 0;
}