Cod sursa(job #629602)

Utilizator giuliastefGiulia Stef giuliastef Data 3 noiembrie 2011 16:00:29
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <cstring>
#define BAZA 67
#define LMAX 2000011 
#define P 1000007
#define Q 2000007
using namespace std;
char A[LMAX],B[LMAX];
int m,n,poz[LMAX],sol,p1[LMAX],p2[LMAX],a1,b1,a2,b2;
void puteri(int l){
	int i;
	p1[0]=1;
	p2[0]=1;
	for(i=1;i<=l;i++){
		p1[i]=(p1[i-1]*BAZA)%P;
		p2[i]=(p2[i-1]*BAZA)%Q;
	}
}
inline int numar(char c)
{
	if(c>='a'&&c<='z') return (c-'a'+1);
	if(c>='A'&&c<='Z') return (c-'A'+27);
	return (c-'0'+53);
} 
void read(){
	ifstream f("strmatch.in");
	f>>B>>A;
	m=strlen(A);
	n=strlen(B);
	puteri(n);
}
void hash(char v[LMAX],int l, int &nr1, int &nr2)
{
	int i;
	nr1=0; nr2=0;
	for(i=0;i<l;i++){
		nr1=(nr1+p1[l-i-1]*numar(v[i])%P)%P;
		nr2=(nr2+p2[l-i-1]*numar(v[i])%Q)%Q;
	}
}
void solve(){
	int i,j,ok;
	hash(B,n,a1,a2);
	hash(A,n,b1,b2);
	if(a1==b1 && a2==b2) 
		poz[++sol]=0;
	for(i=0;i<m-n;i++){
		b1=(P+b1-(p1[n-1]*numar(A[i]))%P)%P;
		b1=(b1*BAZA)%P;
		b1=(b1+numar(A[i+n]))%P;
		b2=(Q+b2-(p2[n-1]*numar(A[i]))%Q)%Q;
		b2=(b2*BAZA)%Q;
		b2=(b2+numar(A[i+n]))%Q;
		if(a1==b1 && a2==b2) 
			poz[++sol]=i+1;
	}
}
void write(){
	int i;
	ofstream g("strmatch.out");
	g<<sol<<"\n";
	for(i=1;i<=sol && i<=1000;i++)
		g<<poz[i]<<" ";
}
int main(){
	read();
	solve();
	write();
	return 0;
}