Cod sursa(job #2223746)

Utilizator david.sachelarieDavid Sachelarie david.sachelarie Data 21 iulie 2018 13:50:18
Problema Potrivirea sirurilor Scor 16
Compilator c Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>
#include <stdlib.h>

char v[2000000],mask[2000000];
int nrmask[2000001];
int poz[1000];

void searchPrefixes(int n){
    int i=0,j=2;
    while(j<=n){
        if(mask[i]==mask[j-1]){
            while(mask[i]==mask[j-1] && j<=n){
                i++; j++;
            }
            j--;
        }
        nrmask[j]=i;
        j++; i=0;
    }

}

int doKmp(int n,int m){
    int i;
    int j=0;
    int nr=0;
    for(i=0;i<n && nr<1000;i++){
        if(j==m-1 && v[i]==mask[j]){
            poz[nr]=i-m+1;
            nr++;
            j=nrmask[j+1];
        }
        else if(v[i]==mask[j]) j++;
        else if(nrmask[j]!=0) j=nrmask[j];
        else j=0;
    }
    if(j==m && nr<1000){
        poz[nr]=i-m;
        nr++;
    }
    return nr;
}

int main()
{
    FILE*fin,*fout;
    fin = fopen("strmatch.in" ,"r");
    fout = fopen("strmatch.out" ,"w");

    char a;
    int i=0;
    a=fgetc(fin);
    while(a!='\n'){
        mask[i]=a;
        i++;
        a=fgetc(fin);
    }
    int m=i;

    a=fgetc(fin);
    i=0;
    while(a!='\n' && a!=EOF){
        v[i]=a;
        i++;
        a=fgetc(fin);
    }
    int n=i;

    searchPrefixes(m);

    int nr=doKmp(n,m);

    fprintf(fout, "%d\n" ,nr);
    for(i=0;i<nr;i++)
        fprintf(fout, "%d " ,poz[i]);
    fprintf(fout, "\n");

    fclose(fin);
    fclose(fout);
    return 0;
}