Cod sursa(job #2062979)

Utilizator clau_rClaudia clau_r Data 10 noiembrie 2017 23:27:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <string.h>

#define MAXN 2000001

#define P 73
#define MOD1 100007
#define MOD2 100009

char a[MAXN], b[MAXN];

char match[MAXN];

int main()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    
    scanf("%s %s", a, b);
    int n = strlen(a);
    int m = strlen(b);
    int hashA1=0, hashA2=0, hash1=0, hash2=0, P1 = 1, P2 = 1, nr = 0;
    
    if (n > m) {
        printf("0\n");
        return 0;
    }
    
    for (int i = 0; i< n; ++i) {
        hashA1 = (hashA1 * P + a[i]) % MOD1;
        hashA2 = (hashA2 * P + a[i]) % MOD2;
        
        hash1 = (hash1 * P + b[i]) % MOD1;
        hash2 = (hash2 * P + b[i]) % MOD2;
        
        if (i != 0) {
            P1 = (P1 * P) % MOD1;
            P2 = (P2 * P) % MOD2;
        }
    }
    
    if (hash1 == hashA1 && hash2 == hashA2) {
        match[0] = 1; ++nr;
    }
    
    for (int i = n; i < m; ++i) {
        hash1 = ((hash1 + MOD1 - (b[i-n] * P1) % MOD1) * P + b[i]) % MOD1;
        hash2 = ((hash2 + MOD2 - (b[i-n] * P2) % MOD2) * P + b[i]) % MOD2;
        
        if (hash1 == hashA1 && hash2 == hashA2) {
            match[i-n+1] = 1; ++nr;
        }
    }
    
    printf("%d\n", nr);
    nr = 0;
    for (int i = 0; i < m &&  nr < 1000; ++i)
        if (match[i])
        { ++nr; printf("%d ", i);}
    printf("\n");
    
    return 0;
}