Cod sursa(job #629457)

Utilizator giuliastefGiulia Stef giuliastef Data 3 noiembrie 2011 13:44:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#define BAZA 67
#define LMAX 2000000
#define P 1000007
using namespace std;
char A[LMAX],B[LMAX];
int m,n,nr1,nr2,b[LMAX],poz[LMAX],sol;
void puteri(int l){
	int i;
	b[0]=1;
	for(i=1;i<=l;i++)
		b[i]=(b[i-1]*BAZA)%P;	
}
void read(){
	ifstream f("strmatch.in");
	f>>B>>A;
	m=strlen(A);
	n=strlen(B);
	puteri(n);
}
int hash(char v[LMAX],int l)
{
	int i,nr=0;
	for(i=0;i<l;i++){
		if(v[i]>='a' && v[i]<='z')
			nr=nr+b[l-i-1]*(v[i]-'a'+1)%P;
		if(v[i]>='A' && v[i]<='Z')
			nr=nr+b[l-i-1]*(v[i]-'A'+27)%P;
		if(v[i]>='0' && v[i]<='9')
			nr=nr+b[l-i]*(v[i]-'0'+53)%P; 
	}
	return nr;
}
void solve(){
	int i;
	nr1=hash(B,n);
	nr2=hash(A,n);
	if(nr1==nr2) poz[++sol]=0;
	for(i=0;i<m-n;i++){
		if(A[i]>='a' && A[i]<='z')
			nr2=nr2-b[n-1]*(A[i]-'a'+1)%P;
		if(A[i]>='A' && A[i]<='Z')
			nr2=nr2-b[n-1]*(A[i]-'A'+27)%P;
		if(A[i]>='0' && A[i]<='9')
			nr2=nr2-b[n-1]*(A[i]-'0'+53)%P;
		nr2=nr2*BAZA%P;
		if(A[i+n]>='a' && A[i+n]<='z')
			nr2=nr2+A[i+n]-'a'+1;
		if(A[i+n]>='A' && A[i+n]<='Z')
			nr2=nr2+A[i+n]-'A'+27;
		if(A[i+n]>='0' && A[i+n]<='9')
			nr2=nr2+A[i+n]-'0'+53;
		if(nr1==nr2) poz[++sol]=i+1;
	}
}
void write(){
	int i;
	ofstream g("strmatch.out");
	g<<sol<<"\n";
	for(i=1;i<=sol;i++)
		g<<poz[i]<<" ";
}
int main(){
	read();
	solve();
	write();
	return 0;
}