Cod sursa(job #579260)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 11 aprilie 2011 23:19:03
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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 hash1, hash2, T1, T2, P1, P2;

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

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

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

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();
    if(NA > NB)
    {
        printf("0\n");
        return 0;
    }
    TakeOff();
    solve();
    UnLoad();
    return 0;
}