Cod sursa(job #1009254)

Utilizator teoionescuIonescu Teodor teoionescu Data 12 octombrie 2013 18:59:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000005;
const int MOD1 = 110503;
const int MOD2 = 104325;
const int a = 62;
char A[Nmax],B[Nmax];
int N,M;
int hashA1,hashB1,alam1=1;
int hashA2,hashB2,alam2=1;
int sol[1005],rasp;
int toi(char c){
    if('0'<=c && c<='9') return (int)(c-'0');
    if('a'<=c && c<='z') return (int)(c-'a')+10;
    if('A'<=c && c<='Z') return (int)(c-'A')+36;
}
void checkEq(int i){
    if(hashA1==hashB1 && hashA2==hashB2){
        rasp++;
        if(rasp<=1000) sol[rasp]=i-M+1;
    }
}
int main(){
    int i;
    in.getline(B,Nmax);
    in.getline(A,Nmax);
    N=strlen(A);
    M=strlen(B);
    for(i=0;i<M;i++){
        hashA1=(hashA1*a+toi(A[i]))%MOD1;
        hashB1=(hashB1*a+toi(B[i]))%MOD1;
        hashA2=(hashA2*a+toi(A[i]))%MOD2;
        hashB2=(hashB2*a+toi(B[i]))%MOD2;
        alam1=(alam1*a)%MOD1;
        alam2=(alam2*a)%MOD2;
    }
    checkEq(i-1);
    for(;i<N;i++){
        hashA1=((hashA1*a)%MOD1+(-(alam1*toi(A[i-M]))%MOD1+MOD1)+toi(A[i]))%MOD1;
        hashA2=((hashA2*a)%MOD2+(-(alam2*toi(A[i-M]))%MOD2+MOD2)+toi(A[i]))%MOD2;
        checkEq(i);
    }
    out<<rasp<<'\n';
    for(i=1;i<=(rasp<1000?rasp:1000);i++) out<<sol[i]<<' ';
    return 0;
}