Cod sursa(job #918261)

Utilizator predator5047Butiu Alexandru Octavian predator5047 Data 18 martie 2013 18:50:06
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
//#ifndef LINUX
//#include "stdafx.h"
//#endif
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const char *in = "strmatch.in", *out = "strmatch.out";
const int P = 101, MOD1 = 100007, MOD2 = 100021;
int nr = 0;
string A, B;
vector<int> v;

void citire() {
	ifstream fin(in);
	fin >> A >> B;

}

void afisare() {
	ofstream fout(out);
	fout << nr << "\n";
	for(int i = 0; i < v.size(); ++i)
		fout << v[i] << " ";
}

void solve() {
	int N = A.size(), M = B.size();
	int P1 = 1;
	int hashA = 0;
	for(int i = 0; i < N; ++i) {
		hashA = (hashA * P + A[i]) % MOD1;
		if(i != 0)
			P1 = (P1 * P) % MOD1;
	}

	int hash1 = 0;
	for(int i = 0; i < N; ++i) 
		hash1 = (hash1 * P + B[i]) % MOD1;

	if(hash1 == hashA && equal(A.begin(), A.end(), B.begin()))
		v.push_back(0);

	for(int i = N; i < M; ++i) {
		hash1 = ( (hash1 - (B[i - N] * P1) % MOD1 + MOD1) * P + B[i] ) % MOD1;

		if(v.size() < 1000 && hash1 == hashA)
			if(equal(A.begin(), A.end(), B.begin() + i - N + 1)) {
				v.push_back(i - N + 1);
				++nr;
			}
	}

}

int main() {
	citire();
	solve();
	afisare();
	return 0;
}