Cod sursa(job #143608)

Utilizator DastasIonescu Vlad Dastas Data 26 februarie 2008 18:26:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#include <cstring>

const int maxn = 2000004;

FILE *in = fopen("strmatch.in","r"), *out = fopen("strmatch.out","w");

int n, m;
char a[maxn], b[maxn];
int pi[maxn];
int v[1002];

void makepi()
{
    for ( int i = 2, k = 0; i <= n; ++i )
    {
        while ( k && a[k+1] != a[i] )
            k = pi[k];

        if ( a[k+1] == a[i] )
            ++k;

        pi[i] = k;
    }
}

int main()
{
    fscanf(in, "%s", a + 1);
    fscanf(in, "%s", b + 1);

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

    makepi();

    int cnt = 0;
    for ( int k = 0, i = 1; i <= m; ++i )
    {
        while ( k && a[k+1] != b[i] )
            k = pi[k];

        if ( a[k+1] == b[i] )
            ++k;

        if ( k == n )
        {
            v[++cnt] = i - n;
            k = pi[n];

            if ( cnt == 1000 )
                break;
        }
    }

    fprintf(out, "%d\n", cnt);
    for ( int i = 1; i <= cnt; ++i )
        fprintf(out, "%d ", v[i]);

	return 0;
}