Cod sursa(job #541967)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 25 februarie 2011 17:08:51
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define FIN "strmatch.in"
#define FOUT "strmatch.out"

#define MAX 2000001
#define P1 100003
#define P2 666013
#define Size 63

int L, R1, R2;

char A[MAX], B[MAX];

vector <int> H;

inline char cod(char X)
{
    if (X >= '0' && X <= '9')
        return 1 + X - '0';

    if (X >= 'a' && X <= 'z')
        return 11 + X - 'a';

    return 37 + X - 'A';
}

int main()
{
    int i, x1, x2, y1, y2;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    gets(B);
    gets(A);
    L = strlen(B) - 1;

    for (i = R1 = R2 = 1; i < L; ++ i)
    {
        R1 = (R1 * Size) % P1;
        R2 = (R2 * Size) % P2;
    }

    for (i = y1 = y2 = 0; i < L; ++ i)
    {
        y1 = (y1 * Size + cod(B[i])) % P1;
        y2 = (y2 * Size + cod(B[i])) % P2;
    }

    for (i = x1 = x2 = 0; A[i]; ++ i)
    {
        if (i >= L)
        {
            x1 = (P1 + x1 - (cod(A[i - L]) * R1) % P1) % P1;
            x2 = (P2 + x2 - (cod(A[i - L]) * R2) % P2) % P2;
        }

        x1 = (x1 * Size + cod(A[i])) % P1;
        x2 = (x2 * Size + cod(A[i])) % P2;

        if (i >= L - 1 && x1 == y1 && x2 == y2)
            H.push_back(i - L + 1);
    }

    printf("%d\n", H.size());

    for (i = 0; i < H.size() & i < 1000; ++ i)
        printf("%d ", H[i]);
    //printf("\n");
}