Cod sursa(job #1839612)

Utilizator manciu_ionIon Manciu manciu_ion Data 3 ianuarie 2017 10:35:39
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cstring>

#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005

using namespace std;

int M, N;
char A[NMax], B[NMax];
int pi[NMax], pos[1024];

ifstream in("strmatch.in");
ofstream out("strmatch.out");

void make_prefix()
{
    int i, q = -1;

    for (i = 1, pi[0] = 0; i < M; ++i)
    {
        while ((q > 0) and (A[q+1] != A[i]))
            q = pi[q];
        if (A[q+1] == A[i])
            ++q;
        pi[i] = q;
    }
}

int main(void)
{
    int i, q = -1, n = 0;

    in >> A; //cout << A << '\n';
    in >> B; //cout << B << '\n';

    M = strlen(A);
    N = strlen(B);

    make_prefix();

    for (i = 1; i < N; ++i)
    {
        while ((q > 0) and (A[q+1] != B[i]))
            q = pi[q];
        if (A[q+1] == B[i])
            ++q;
        if (q == M - 1)
        {
            q = pi[q];
            ++n;
            if (n <= 1000)
                pos[n] = i - M + 1;
        }
    }

    out << n << '\n';
    for (i = 1; i <= minim(n, 1000); ++i)
        out << pos[i] << " ";
    out << '\n';

    return 0;
}