Cod sursa(job #1377138)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 5 martie 2015 20:20:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define NMAX 2000005

using namespace std;

int T[NMAX], nrap, afis[NMAX], lA, lB;
char A[NMAX], B[NMAX];

void citire()
{
    A[0] = B[0] = '#';
    scanf("%s", A + 1);
    scanf("%s", B + 1);
    lA = strlen(A) - 1;
    lB = strlen(B) - 1;
}

void prefix()
{
    int q = 0;
    for (int i = 2; i <= lA; ++i)
    {
        T[i] = 0;
        while (q && A[i] != A[q + 1])
            q = T[q];
        if (A[i] == A[q + 1])
            q++;
        T[i] = q;
    }
}

void kmp()
{
    int q = 0;
    for (int i = 1; i <= lB; ++i)
    {
        while (q && B[i] != A[q + 1])
            q = T[q];
        if (B[i] == A[q + 1])
            q++;
        if (q == lA)
        {
            q = T[q];
            nrap++;
            if (nrap <= 1000)
                afis[nrap] = i - lA;
        }
    }
}

void afisare()
{
    int cnt = min(nrap, 1000);
    printf("%d\n", nrap);
    for (int i = 1; i <= cnt; ++i)
        printf("%d ", afis[i]);
}

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

    citire();
    prefix();
    kmp();
    afisare();

    return 0;
}