Cod sursa(job #1011481)

Utilizator sziliMandici Szilard szili Data 16 octombrie 2013 21:28:48
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.55 kb
#include <stdio.h>
#include <stdlib.h>

char s1[2000001];
char s2[2000001];
int pi[2000001];
int solutions[2000001];

void readData(){
    char c;

    int i=1;
    s1[0] = ' ';
    s2[0] = ' ';

    do {
        scanf("%c", &c);

        s1[i++] = c;
    } while (c != '\n');

    s1[--i] ='\0';

    i=1;

    do {
        scanf("%c", &c);

        s2[i++] = c;
    } while (c != '\n' && c != EOF);

    s2[--i] ='\0';
}

void buildPrefixTable(){
    //build the prefix table for the first, smaller string
    int k=0;
    int q = 1;
    pi[1] = 0;

    int m = strlen(s1) - 1;

    for (q=2; q <=m; q++) {

        while (k>0 && s1[k+1] != s1[q]){
            k = pi[k];
        }

        if (s1[k+1] == s1[q]){
            k++;
        }
        pi[q] = k;
    }

}

void kmp(){
    int foundNr = 0;


    int n  = strlen(s2) - 1;
    int m = strlen(s1) - 1;

    int q = 0;

    for (int i=1; i<=n; i++){

        while (q > 0 && s1[q+1] != s2[i]){
            q = pi[q];
        }

        if (s1[q+1] == s2[i]){
            q++;

            if (q == m){
                q = pi[q];
                solutions[foundNr] = i;
                foundNr++;
            }
        }

    }

    printf("%d\n", foundNr);
    for (int i=0; i<foundNr; i++){
        printf("%d ", solutions[i] - strlen(s1) + 1);
    }

}


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

    readData();

    buildPrefixTable();

    kmp();

    return 0;
}