Cod sursa(job #101335)

Utilizator scvalexAlexandru Scvortov scvalex Data 13 noiembrie 2007 13:35:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.72 kb
#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;
}