Cod sursa(job #1011540)

Utilizator sziliMandici Szilard szili Data 16 octombrie 2013 22:07:48
Problema Potrivirea sirurilor Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 1.79 kb
#include <stdio.h>
#include <stdlib.h>


char s1[2000001];
char s2[2000001];
int pi[2000001];
int solutions[2000001];
int n=1,m=1;

int mini(int a, int b){
    if (a<b)
        return a;
    else
        return b;
}

void readData(){
    char c;
    int i=1;

    fgets(s1, sizeof(s1), stdin);

    i=1;

    while ((s1[i] <='Z' && s1[i] >= 'A') || (s1[i] <= 'z' && s1[i] >= 'a') || (s1[i] >= '0' && s1[i] <= '9') ){
        i++;
    }
    m = i;

    fgets(s2, sizeof(s2), stdin);

    i=1;

    while ((s2[i] <='Z' && s2[i] >= 'A') || (s2[i] <= 'z' && s2[i] >= 'a') || (s2[i] >= '0' && s2[i] <= '9') ){
        i++;
    }
    n = i;

    for (int i=n-1; i>=0; i--){
        s2[i+1] = s2[i];
    }


    for (int i=m-1; i>=0; i--){
        s1[i+1] = s1[i];
    }



}

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

    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 q = 0;

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

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

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

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

    printf("%d\n", foundNr);
    for (int i=0; i<mini(foundNr, 1000); i++){
            printf("%d ", solutions[i]);
    }

}


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

    readData();

    buildPrefixTable();

    kmp();

    return 0;
}