Cod sursa(job #1183183)

Utilizator MarianMMorosac George Marian MarianM Data 8 mai 2014 16:43:15
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <string>
#include <vector>
#include <list>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define PRIME1 100007
#define PRIME2 100021
#define D 123

string P, T;
int hashP1, hashT1, h1 = 1;
int hashP2, hashT2, h2 = 1;
vector<int> s;	int nos;

int main(){
	int i, lgP, shift; char x;

	fin >> P; lgP = P.size();
	for (i = 0; i < lgP; i++) 
		hashP1 = (D * hashP1 + P[i]) % PRIME1,
		hashP2 = (D * hashP2 + P[i]) % PRIME2;
	
	fin.get(x); 
	for (i = 0; i < lgP && !fin.eof(); i++){
		fin.get(x); T += x;
		hashT1 = (D * hashT1 + T[i]) % PRIME1,
		hashT2 = (D * hashT2 + T[i]) % PRIME2;
	}
	
	for (i = 1; i < lgP; i++) 
		h1 = (h1 * D) % PRIME1,
		h2 = (h2 * D) % PRIME2;

	if (lgP < T.size()) fout << "0\n";
	
	shift = 0;
	while (!fin.eof()){
		if (hashP1 == hashT1 && hashP2 == hashT2){
				for (i = 0; i < lgP; i++)	if (P[i] != T[i + shift])	break;
				if (i == lgP){
					nos++; 
					if (nos <= 1000)
						s.push_back(shift);
				}
			}

		fin.get(x); T += x;
		hashT1 = ((hashT1 - (T[shift] * h1) % PRIME1 + PRIME1)*D + x) % PRIME1;
		hashT2 = ((hashT2 - (T[shift] * h2) % PRIME2 + PRIME2)*D + x) % PRIME2;
		shift++;
	}

	fout << nos << '\n';
	for (i = 0; i < s.size() && i < 1000; i++) fout << s[i] << ' ';

	return 0;
}