Cod sursa(job #100673)

Utilizator scvalexAlexandru Scvortov scvalex Data 12 noiembrie 2007 16:29:11
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

string text;
vector<unsigned long> cs;

void calc_cksum(int n) {
	unsigned long c = 0;
	int i(0);
	unsigned long p = 1;
	for (; i < n; ++i) {
		c += (text[i] - 'a') * p;
		p *= 3;
	}
	p /= 3;
	cs.insert(cs.begin(), text.size() - n + 1, 0);
	cs[0] = c;
	for (; i < (int)text.size(); ++i) {
		c /= 3;
		c += p * (text[i] - 'a');
		cs[i - n + 1] = c;
	}
}

unsigned long inline cksum(const string &s) {
	unsigned long c = 0;
	unsigned long p = 1;
	for (int i(0); i < (int)s.size(); ++i) {
		c += (s[i] - 'a') * p;
		p *= 3;
	}
	return c;
}

int main(int argc, char *argv[]) {
	ifstream fin("abc2.in");
	fin >> text;
	bool notCalculated(true);
	int tot(0);
	do {
		string aux;
		fin >> aux;
		if (!aux.empty()) {
			if (notCalculated) {
				calc_cksum(aux.size());
// 				for (int i(0); i < (int)cs.size(); ++i)
// 					cout << cs[i] << " ";
// 				cout << endl;
				notCalculated = false;
			}

			unsigned long c = cksum(aux);
// 			cout << c << endl;

			for (int i(0); i < (int)cs.size(); ++i)
				if (c == cs[i]) {
					cs[i] = -1;
					++tot;
				}
		}
	} while (!fin.eof());
	fin.close();

	ofstream fout("abc2.out");
	fout << tot << endl;
	fout.close();

	return 0;
}