Cod sursa(job #911438)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 11 martie 2013 18:08:40
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
#include <string.h>
#include <list>
using namespace std;

#define Nmax 2000005
#define Mod1 100007
#define Mod2 100021

char A[Nmax], B[Nmax];
int n, m, sol, nrsol;
list <int> position;

void read(){
    scanf("%s %s", A+1, B+1);
    n = strlen(A+1);
    m = strlen(B+1);
    fclose(stdin);
}

void Rabin_Karp(){
    unsigned int p1, p2, b, hA1, hA2, hB1, hB2;
    b = 63; p1 = p2 = 1;
    hA1 = hA2 = hB1 = hB2 = 0;
    for(int i = 1; i <= n; ++i){
        hA1 = (hA1*b + A[i])%Mod1;
        hA2 = (hA2*b + A[i])%Mod2;
        hB1 = (hB1*b + B[i])%Mod1;
        hB2 = (hB2*b + B[i])%Mod2;
        p1  = (p1*b)%Mod1;
        p2  = (p2*b)%Mod2;
    }
    if(hA1 == hB1 && hA2 == hB2){
        ++sol;
        ++nrsol;
        position.push_back(0);
    }
    for(int i = 2; i <= m-n+1; ++i){
        hB1 = ( hB1*b - (B[i-1]*p1)%Mod1 + Mod1 + B[i+n-1] )%Mod1;
        hB2 = ( hB2*b - (B[i-1]*p2)%Mod2 + Mod2 + B[i+n-1] )%Mod2;
        if(hA1 == hB1 && hA2 == hB2){
            ++sol;
            if(nrsol < 1000){
                ++nrsol;
                position.push_back(i-1);
            }
        }
    }
}

void write(){
    printf("%i\n", sol);
    list <int>::iterator it;
    for(it = position.begin(); it != position.end(); ++it)
        printf("%i ", *it);
}

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    read();
    Rabin_Karp();
    write();

    return 0;
}