Cod sursa(job #992519)

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

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

const int MAX = 2501000;

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

long long mod1 = 100005, mod2 = 666013;
long long ch1 = 277, ch2 = 281;
long long 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 = key1 * ch1 + a[i];
		key1 = key1 % mod1;
		key2 = key2 * ch2 + a[i];
		key2 = key2 % mod2;
	}
	
	long long p1, p2; p1 = p2 = 1;
	for (int i = 1; i <= l1; ++i)
		p1 = (p1 * ch1) % mod1, p2 = (p2 * ch2) % mod2;
	
	long long c1, c2; c1 = c2 = 0;
	for (int i = 1; i <= l2; ++i) {
		c1 = c1 * ch1 + b[i];
		c1 = c1 % mod1;
		
		c2 = c2 * ch2 + b[i];
		c2 = c2 % mod2;
		
		if (i > l1) {
			c1 = (c1 - p1 * b[i - l1]) % mod1;
			if (c1 < 0)
				c1 += mod1;
			c2 = (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();
}