Cod sursa(job #955110)

Utilizator cousin.batmanVaru Batman cousin.batman Data 30 mai 2013 20:58:29
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
#include<string.h>
#define NMax 2000001

char pattern[NMax], text[NMax], d;
int pi[NMax], pn = 0, result[1024];
int n,m;

int main(){
    int i, k=0;
    FILE *f = fopen("strmatch.in", "r");
    FILE *g = fopen("strmatch.out", "w");

    do { fscanf(f, "%c", pattern+n); } while(pattern[n++]!='\n');
    do { fscanf(f, "%c", text+m); m++; }while(!feof(f));
    n--; m-=2;

    //CREATE PI
    pi[0] = 0;

    for(i=1; i<n; i++){
        while(k>0 && pattern[i]!=pattern[k])
            k=pi[k];

        if(pattern[i]==pattern[k])
            k++;
        pi[i] = k;
    }

    //FIND RESULTS
    k=0;
    for(i=0; i<m; i++){
        while(k>0 && text[i]!=pattern[k])
            k=pi[k-1];
        if(text[i] == pattern[k])
            k++;

        if(k==n){
            if(pn<1000)
                result[pn] = i-n+1;
            k=pi[k-1];
            pn++;
        }
    }

    fprintf(g, "%d\n", pn);
    if(pn>1000) pn =1000;
    for(i=0; i<pn; i++)
        fprintf(g, "%d ", result[i]);

    return 0;
}