Cod sursa(job #579262)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 11 aprilie 2011 23:23:34
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <fstream>
#include <string.h>

using namespace std;

const int nmax = 2000010;
const int P = 73;
const int Mod1 = 100007;
const int Mod2 = 100021;
char A[nmax], B[nmax];
int match[nmax], NA, NB;

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

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

    NA = strlen(A);
    NB = strlen(B);

    if(NA > NB)
    {
        printf("0\n");
        return 0;
    }

    int hash1, hash2, T1, T2, P1, P2, i, Nr = 0;
    P1 = P2 = 1;
    hash1 = hash2 = A[0];
    T1 = T2 = B[0];
    for(i = 1; i < NA; i++)
    {
        T1 = ((T1 * P) % Mod1 + B[i]) % Mod1;
        T2 = ((T2 * P) % Mod2 + B[i]) % Mod2;
        hash1 = ((hash1 * P) % Mod1 + A[i]) % Mod1;
        hash2 = ((hash2 * P) % Mod2 + A[i]) % Mod2;
        P1 = (P1 * P) % Mod1;
        P2 = (P2 * P) % Mod2;
    }

    if(hash1 == T1 && hash2 == T2)
        match[0] = 1, Nr++;

    for(i = NA; i < NB; i++)
    {
        T1 = ((T1 - (P1 * B[i - NA]) % Mod1 + Mod1) * P + B[i]) % Mod1;
        T2 = ((T2 - (P2 * B[i - NA]) % Mod2 + Mod2) * P + B[i]) % Mod2;

        if(T1 == hash1 && T2 == hash2)
            match[i - NA + 1] = 1, Nr++;
    }

    printf("%d\n", Nr);
    Nr = 0;
    for(i = 0; i < NB && Nr < 1000; i++)
        if(match[i])
            printf("%d ", i), Nr++;

    return 0;
}