Cod sursa(job #1011507)

Utilizator sziliMandici Szilard szili Data 16 octombrie 2013 21:49:35
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.72 kb
#include <stdio.h>
#include <stdlib.h>


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

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

void readData(){
    char c;

    gets(s1, sizeof(s1), )
    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 && 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++;

            if (foundNr >= 1000){
                break;
            }

        }
    }

    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;
}