Cod sursa(job #549432)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 8 martie 2011 16:29:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

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

#define MAX 2000001
#define P1 (1 << 22) - 1
#define Size 61

int L, R1, R2;

char A[MAX], B[MAX], cod[256];

vector <int> H;

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

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

    for (i = 0; i <= 9; ++ i)
        cod[i + '0'] = i + 1;
    for (i = 0; i < 26; ++ i)
        cod[i + 'a'] = 11 + i;
    for (i = 0; i < 26; ++ i)
        cod[i + 'A'] = 37 + i;

    scanf("%s %s", &B, &A);
    L = strlen(B);

    for (i = R1 = 1; i < L; ++ i)
        R1 = (R1 * Size) & P1;

    for (i = y1 = 0; i < L; ++ i)
        y1 = (y1 * Size + cod[B[i]]) & P1;

    for (i = x1 = 0; A[i]; ++ i)
    {
        if (i >= L)
            x1 = (P1 + 1 + x1 - ((cod[A[i - L]] * R1) & P1)) & P1;

        x1 = (x1 * Size + cod[A[i]]) & P1;

        if (i >= L - 1 && x1 == y1)
            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");
}