Cod sursa(job #1095128)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 30 ianuarie 2014 14:33:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <stdio.h>
#include <string.h>

#define Nmax 2000005

char a[Nmax], b[Nmax];
int n, m, sol, c;
int pi[Nmax], where[Nmax];

void read()
{
    freopen("strmatch.in", "r", stdin);
    scanf("%s", a + 1);
    scanf("%s", b + 1);

    n = strlen(a + 1);
    m = strlen(b + 1);

    fclose(stdin);
}

void kmp()
{
    int k;
    k = 0;
    for (int i = 2; i <= n; ++i){
        while (k > 0 && a[k + 1] != a[i])
            k = pi[k];
        if (a[k + 1] == a[i])
            ++k;
        pi[i] = k;
    }

    k = 0;

    for (int i = 1; i <= m; ++i){
        while (k > 0 && a[k + 1] != b[i])
            k = pi[k];
        if (a[k + 1] == b[i])
            ++k;
        if (k == n && sol < 1000) {
            ++sol;
            where[c++] = i - n;
        }
    }
}

void write()
{
    freopen("strmatch.out", "w", stdout);
    printf("%d\n", sol);
    for (int i = 0; i < c; ++i)
        printf("%d ", where[i]);
}

int main()
{
    read();
    kmp();
    write();

    return 0;

}