Cod sursa(job #1920641)

Utilizator 1475369147896537415369Andrei Udriste 1475369147896537415369 Data 10 martie 2017 08:53:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <string.h>

#define BASE 73
#define MOD1 100007
#define MOD2 100021

char A[2000000], B[2000000];
int lengthA, lengthB;
bool match[2000000];

int hashA1, hashA2;
int power1 = 1, power2 = 1;
int hash1, hash2, matches;

int main(){

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

    scanf("%s %s", A, B);

    lengthA = strlen(A);
    lengthB = strlen(B);

    if(lengthA > lengthB){
        printf("0\n");
        return 0;
    }

    for(int i = 0; i < lengthA; i++){

        hashA1 = (hashA1 * BASE + A[i]) % MOD1;
        hashA2 = (hashA2 * BASE + A[i]) % MOD2;

        if(i != 0){
            power1 = (power1 * BASE) % MOD1;
            power2 = (power2 * BASE) % MOD2;
        }
    }

    for(int i = 0; i < lengthA; i++){
        hash1 = (hash1 * BASE + B[i]) % MOD1;
        hash2 = (hash2 * BASE + B[i]) % MOD2;
    }

    if(hash1 == hashA1 && hash2 == hashA2){
        match[0] = true;
        matches++;
    }

    for(int i = lengthA; i < lengthB; i++){

        hash1 = ((hash1 - (B[i - lengthA] * power1) % MOD1 + MOD1) * BASE + B[i]) % MOD1;
        hash2 = ((hash2 - (B[i - lengthA] * power2) % MOD2 + MOD2) * BASE + B[i]) % MOD2;

        if(hash1 == hashA1 && hash2 == hashA2){
            match[i - lengthA + 1] = true;
            matches++;
        }
    }
    printf("%d\n", matches); matches = 0;

    for (int i = 0; i < lengthB && matches < 1000; i++){
        if(match[i] == true){
            matches++;
            printf("%d ", i);
        }
    }
    return 0;
}