Cod sursa(job #1148689)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 20 martie 2014 23:38:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 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;
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);

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