Cod sursa(job #581360)

Utilizator varuvasiTofan Vasile varuvasi Data 14 aprilie 2011 00:32:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <stdio.h>
#include <string.h>
#define maxn 2000022

char A[maxn], B[maxn];
int pi[maxn], pos[1033];
int matches;

/*
Ce faci Andradaaaaaaaaa
aaaaaaa
aaaaaaaaaa
aaaaaaaaa
aaaaaa
Da bine Mo, uite...
*/

void match()
{
    int lena = strlen(A), lenb = strlen(B);
    int i = 0, j = 0;
    for (i = 0; i <= lenb - lena; i++)
    {
        j = 0;
        while (j < lena && A[j] == B[i+j])
            j++;
        if (j == lena)
            if (matches > 1000)
                matches++;
            else
                pos[matches++] = i;
    }
}

void prefix()
{
    int i = 0, k = 0, lena = strlen(A);
    pi[1] = 0;
    for (i = 2; i <= lena; i++)
    {
        while (k > 0 && A[k] != A[i - 1])
            k = pi[k];
        if (A[k] == A[i - 1])
            k++;
        pi[i] = k;
    }
    //for (i = 1; i <= lena; i++)
    //    printf("%d ", pi[i]);
}

void match_kmp()
{
    int lena = strlen(A), lenb = strlen(B);
    int i = 0, q = 0;
    for (i = 0; i < lenb; i++)
    {
        while (q > 0 && A[q] != B[i])
            q = pi[q];
        if (A[q] == B[i])
            q = q + 1;
        //printf("%d %d\n", i, q);
        if (q == lena)
            if (matches > 1000)
                matches++;
            else
                pos[matches++] = i - lena + 1;
    }
}

int main()
{
    FILE *fin = fopen("strmatch.in", "rt");
    FILE *fout = fopen("strmatch.out", "wt");
    int i = 0;

    fscanf(fin, "%s\n%s", A, B);
    prefix();
    match_kmp();
    fprintf(fout, "%d\n", matches);
    for (i = 0; i < ((matches > 1000) ? 1000 : matches); i++)
        fprintf(fout, "%d ", pos[i]);

    fclose(fin), fclose(fout);

    return 0;
}