Cod sursa(job #629580)

Utilizator giuliastefGiulia Stef giuliastef Data 3 noiembrie 2011 15:42:24
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <cstring>
#define BAZA 67
#define LMAX 2000011 
#define P 1000007
using namespace std;
char A[LMAX],B[LMAX];
int m,n,poz[LMAX],sol,b[LMAX],nr1,nr2;
void puteri(int l){
	int i;
	b[0]=1;
	for(i=1;i<=l;i++)
		b[i]=(b[i-1]*BAZA)%P;
}
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);
}
int hash(char v[LMAX],int l)
{
	int i,nr=0;
	for(i=0;i<l;i++)
		nr=(nr+b[l-i-1]*numar(v[i])%P)%P;
	return nr;
}
void solve(){
	int i,j,ok;
	nr1=hash(B,n);
	nr2=hash(A,n);
	if(nr1==nr2) {
		/*ok=1;
		for(i=0;i<n;i++)
			if(A[i]!=B[i]) ok=0;
		if(ok) */ poz[++sol]=0;
	}
	for(i=0;i<m-n;i++){
		nr2=(P+nr2-(b[n-1]*numar(A[i]))%P)%P;
		nr2=(nr2*BAZA)%P;
		nr2=(nr2+numar(A[i+n]))%P;
		if(nr1==nr2) {
			/*ok=1;
			for(j=0;j<n;j++)
				if(A[i+j+1]!=B[j]) ok=0;
			if(ok)*/ 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;
}