Cod sursa(job #579255)

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

using namespace std;

const int nmax = 2000100;
const int P = 73;
const int Mod1 = 100003;
const int Mod2 = 100021;
char A[nmax], B[nmax];
int match[nmax], NA, NB;
int hash1, hash2, T1, T2, P1, P2;

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

    fgets(A, sizeof(A), stdin);
    fgets(B, sizeof(B), stdin);

    NA = strlen(A) - 1;
    NB = strlen(B) - 1;
}

void TakeOff()
{
    P1 = P2 = 1;
    int i;
    for(i = 0; 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;
        if(i < NA -1 )
        {
            P1 = (P1 * P) % Mod1;
            P2 = (P2 * P) % Mod2;
        }
    }
}

int Nr;

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

    int i;
    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++;
    }
}

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

int main()
{
    read();
    TakeOff();
    solve();
    UnLoad();
    return 0;
}