Cod sursa(job #1076047)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 9 ianuarie 2014 20:39:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#include<string.h>
 
char A[2000001], B[2000001];
int sol[1024];
 
int rabin_karp(char *S, char *M,int b, int MOD, int MOD2){
	
    int r=0, kM1=M[0], kS1=S[0],kM2=M[0], kS2=S[0], lenS, lenM, i, P1=1, P2=1;
    lenS=strlen(S);
    lenM=strlen(M);
     
    for (i=1; i<lenM; i++){
        kM1=(kM1*b+M[i])%MOD;
        kM2=(kM2*b+M[i])%MOD2;
        kS1=(kS1*b+S[i])%MOD;
        kS2=(kS2*b+S[i])%MOD2;
        P1=(P1*b)%MOD;
        P2=(P2*b)%MOD2;
    }
    if ((kM1==kS1)&&(kM2==kS2)){
        ++r;
        sol[r]=0;
    }
    for (i=lenM; i<lenS; i++){
		
        kS1=((kS1- (S[i-lenM]*P1)%MOD + MOD )  *b+S[i])%MOD;
        kS2=((kS2- (S[i-lenM]*P2)%MOD2+ MOD2)  *b+S[i])%MOD2;
     
         
        if ((kM1==kS1)&&(kM2==kS2))
        {
            ++r;
            if (r<=1001)
                sol[r]=i-lenM+1;
        }
    }
	return r;
}
int main(){
	
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(A);
    gets(B);
    int r,i;
	
    r=rabin_karp(B, A, 128, 100007, 100021);
    printf("%d\n", r);
	
    for (i=1;i<=r && i<=1000;i++){
        printf("%d ", sol[i]);
    }
	
    fclose(stdout);
    return 0;
}