Cod sursa(job #955098)

Utilizator cousin.batmanVaru Batman cousin.batman Data 30 mai 2013 20:52:15
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 0.98 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");

    fgets(pattern, sizeof(pattern), f); n= strlen(pattern);
    fgets(text, sizeof(text), f); m=strlen(text);

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