Cod sursa(job #1148691)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 20 martie 2014 23:45:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

const long nmax = 2000002, base = 256, mod = 666013;
char a[nmax], b[nmax];
long keya, lena, cb=1, keyact, lenb, x;
vector <int> h;

int main(){
	int player_unu=0;

	in>>a;
	lena = strlen(a);
	for(int i = 0; i<lena; i++)
	{
		keya = (keya * base + a[i])%mod;
		if(i>=1){
		cb *= base;
		cb %= mod;}
	}

	in>>b;
	lenb = strlen(b);
	for(int i = 0; i<lenb; i++)
	{
		if(i<lena)
		{
			keyact = (keyact * base + b[i])%mod;
		}
		else
		{
			if(keyact==keya)
				h.push_back(i-lena);
			keyact -= cb*(b[i-lena]);
			keyact %= mod;
			if(keyact<0)
				keyact = mod+keyact;
			keyact = (keyact * base + b[i]);
			keyact %= mod;
		}
	}
	if(keyact==keya)
				h.push_back(lenb-lena);

	x = (int)h.size();
	out<<x<<'\n';
	if(x>1000)
		x=1000;
	for(int i = 0; i<x; i++)
		out<<h[i]<<' ';
	out<<'\n';
	return player_unu;
}