Cod sursa(job #1128139)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 27 februarie 2014 15:35:09
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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 rabinKarp(){
    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("%d\n", sol);
    list <int>::iterator it;
    for(it = position.begin(); it != position.end(); ++it)
        printf("%d ", *it);
}

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

    read();
    rabinKarp();
    write();

    return 0;
}