Cod sursa(job #912625)

Utilizator MciprianMMciprianM MciprianM Data 12 martie 2013 17:05:46
Problema Potrivirea sirurilor Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <cassert>
#include <vector>
#include <cstring>
//#include <iostream>

using namespace std;

static const int MOD = 666013, A = 52, MAXL = 2000009;
vector<int> v;
char s1[MAXL], s2[MAXL];

int dig(char c) {
	int ans = 0;
	assert(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z'));
	if(c >= 'a') {
		ans = (c - 'a') + 26;
	}
	else {
		ans = c - 'A';
	}
	return ans;
}

int main() {
	int i, kt = 0;
	ifstream f("strmatch.in");
	f >> s2 >> s1;
	f.close();
	//cout << s2 << endl;
	//cout << s1 << endl;
	ofstream g("strmatch.out");
	int n1 = strlen(s1);
	int n2 = strlen(s2);
	if(n1 < n2) {
		g << "0\n";
	}
	else {
		int j, hP(0), hT(0), Ap = 1;
		for(i = 0; s2[i]; i++) {
			hP = (hP * A + dig(s2[i])) % MOD;
			//cout << dig(s2[i]) << endl;
		}
		//cout << hP << endl;
		int l = n2 - 1;
		for(i = 0; i < l; i++) {
			hT = (hT * A + dig(s1[i])) % MOD;
			//cout << hT << endl;
			Ap = (Ap * A) % MOD;
		}
		for(i = l; s1[i]; i++) {
			hT = ((hT * A) + dig(s1[i])) % MOD;
			//cout << hT << endl;
			if(hT == hP) {//possible match
				for(j = 0; s2[j]; j++) {
					if(s2[j] != s1[i - l + j]) {
						break;
					}
				}
				if(!s2[j]) {
					if(kt < 1000) {
						v.push_back(i - l);
					}
					kt++;
				}
			}
			hT -= dig(s1[i - l]) * Ap;
			hT = hT % MOD;
			if(hT < 0)	hT += MOD;
		}
		g << kt << '\n';
		for(i = 0; i < (int)v.size(); i++) {
			g << v[i] << ' ';
		}
		if(v.size())	g << '\n';
	}
	g.close();
	return 0;
}