Cod sursa(job #992520)

Utilizator cont_de_testeCont Teste cont_de_teste Data 2 septembrie 2013 00:32:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

const int MAX = 2000100;

int l1, l2;
char a[MAX], b[MAX];

int mod1 = 100005, mod2 = 666013;
int ch1 = 277, ch2 = 281;
int key1, key2;

int sol;
int soln[1010];

int main() {
	fin.getline(a + 1, MAX - 1);
	fin.getline(b + 1, MAX - 1);
	
	l1 = strlen(a + 1);
	l2 = strlen(b + 1);
	
	for (int i = 1; i <= l1; ++i) {
		key1 = (1LL * key1 * ch1 + a[i]) % mod1;
		key2 = (1LL * key2 * ch2 + a[i]) % mod2;
	}
	
	int p1, p2; p1 = p2 = 1;
	for (int i = 1; i <= l1; ++i)
		p1 = (1LL * p1 * ch1) % mod1, p2 = (1LL * p2 * ch2) % mod2;
	
	int c1, c2; c1 = c2 = 0;
	for (int i = 1; i <= l2; ++i) {
		c1 = (1LL * c1 * ch1 + b[i]) % mod1;
		
		c2 = (1LL * c2 * ch2 + b[i]) % mod2;
		
		if (i > l1) {
			c1 = (1LL * c1 - p1 * b[i - l1]) % mod1;
			if (c1 < 0)
				c1 += mod1;
			c2 = (1LL * c2 - p2 * b[i - l1]) % mod2;
			if (c2 < 0)
				c2 += mod2;
		}
		
		if (c1 == key1 && c2 == key2) {
			++sol;
			if (sol <= 1000)
				soln[sol] = i - l1;
		}
	}
	
	fout << sol << '\n';
	for (int i = 1; i <= min(sol, 1000); ++i)
		fout << soln[i] << ' ';
	
	fin.close();
	fout.close();
}