Cod sursa(job #629494)

Utilizator giuliastefGiulia Stef giuliastef Data 3 noiembrie 2011 14:08:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
#include <fstream>
#include <cstring>
#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;	
}
inline int numar(char c){
	int nr;
	switch(c){
case 'a': nr=1;break;
case 'b': nr=2;break;
case 'c': nr=3;break;
case 'd': nr=4;break;
case 'e': nr=5;break;
case 'f': nr=6;break;
case 'g': nr=7;break;
case 'h': nr=8;break;
case 'i': nr=9;break;
case 'j': nr=10;break;
case 'k': nr=11;break;
case 'l': nr=12;break;
case 'm': nr=13;break;
case 'n': nr=14;break;
case 'o': nr=15;break;
case 'p': nr=16;break;
case 'q': nr=17;break;
case 'r': nr=18;break;
case 's': nr=19;break;
case 't': nr=20;break;
case 'u': nr=21;break;
case 'v': nr=22;break;
case 'w': nr=23;break;
case 'x': nr=24;break;
case 'y': nr=25;break;
case 'z': nr=26;break;

case 'A': nr=27;break;
case 'B': nr=28;break;
case 'C': nr=29;break;
case 'D': nr=30;break;
case 'E': nr=31;break;
case 'F': nr=32;break;
case 'G': nr=33;break;
case 'H': nr=34;break;
case 'I': nr=35;break;
case 'J': nr=36;break;
case 'K': nr=37;break;
case 'L': nr=38;break;
case 'M': nr=39;break;
case 'N': nr=40;break;
case 'O': nr=41;break;
case 'P': nr=42;break;
case 'Q': nr=43;break;
case 'R': nr=44;break;
case 'S': nr=45;break;
case 'T': nr=46;break;
case 'U': nr=47;break;
case 'V': nr=48;break;
case 'W': nr=49;break;
case 'X': nr=50;break;
case 'Y': nr=51;break;
case 'Z': nr=52;break;

case '0': nr=53;break;
case '1': nr=54;break;
case '2': nr=55;break;
case '3': nr=56;break;
case '4': nr=57;break;
case '5': nr=58;break;
case '6': nr=59;break;
case '7': nr=60;break;
case '8': nr=61;break;
case '9': nr=62;break;
	}
	return nr;
}
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;
	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;
		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++)
		g<<poz[i]<<" ";
	g<<"\n";
}
int main(){
	read();
	solve();
	write();
	return 0;
}