Cod sursa(job #1776546)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 11 octombrie 2016 15:11:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
# include <bits/stdc++.h>

using namespace std;

const int Nmax = 2000000 + 5;

int pw[Nmax], i, sol = 0, v[1005], hash_a = 0, hash_b = 0, m, n, N;
char x[Nmax], y[Nmax];

void power()
{

    pw[0] = 1;

    for (i = 1; i <= n; ++i)
        pw[i] = pw[i - 1] * 27;

}

void build()
{

    for (i = 1; i <= m; ++i)
        hash_a += x[i] * pw[i];

    for (i = 1; i <= n; ++i)
    {
        hash_b += y[i] * pw[i];

        if (i < m) continue;

        if (hash_a * pw[i - m] == hash_b)
        {
            ++sol;
            if (sol <= 1000) v[++N] = i - m;
        }

        hash_b -= pw[i - m + 1] * y[i - m + 1];

    }

}

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

    gets(x + 1), gets(y + 1);

    m = strlen(x + 1), n = strlen(y + 1);

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

    power();
    build();

    printf("%d\n", sol);

    for (i = 1; i <= N; ++i)
        printf("%d ", v[i]);


    return 0;
}