Cod sursa(job #878144)

Utilizator IronWingVlad Paunescu IronWing Data 14 februarie 2013 02:29:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <cstdio>
#include <cstring>
#include <assert.h>

# define NMAX 2000002

void computePrefixFunction(char *a, int  *pi, int m){

    pi[1] = 0;
    int k  = 0;

    for(int q = 2; q <= m; ++q){
        while (k > 0 && a[k + 1] != a[q]){
            k = pi[k];
        }
        if (a[k + 1] == a[q]){
            ++k;
        }
        pi[q] = k;
    }
}

int pi[NMAX];
char a[NMAX+1], b[NMAX+1];
int matches[1024];

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    int m, n;
    a[0] = ' ', b[0] = ' ';
    fgets(a + 1, NMAX, stdin);
    fgets(b + 1, NMAX, stdin);

    // search a substring into b
    // printf("%s", a);
    // printf("%s", b);

    m = strlen(a) - 2; // get rid of newline and space
    n = strlen(b) - 2; // get rid of newline and space
    computePrefixFunction(a, pi, m);
    //for(int i = 1; i <=m; i++){
    //    printf("%d ", pi[i]);
    //}
    //putchar('\n');

    // kmp
    int matchCount = 0;
    int q = 0; // number of characters matched
    for(int i = 1; i <= n; i++){
        while ( q > 0 && a[q + 1] != b[i]){
            // next character does not match
            q =  pi[q];
        }
        if (a[q + 1] == b[i])
            ++q;
        if (q == m){
            if(matchCount < 1000)
                matches[matchCount++] = i - m;
            q = pi[q]; // look for next mat
        }
    }

    // print matches
    assert(matchCount<=1000);
    printf("%d\n", matchCount);
    for(int i = 0; i < matchCount; ++i){
        printf("%d ", matches[i]);
    }
    putchar('\n');

    return 0;
}