Cod sursa(job #2515748)

Utilizator biopreaOprea Bianca bioprea Data 29 decembrie 2019 15:15:47
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <stdio.h>
#include <string.h>
using namespace std;
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
int p,t,i,j,lps[2000005],nrap,ap[1001],k,lg;
char patt[2000005],txt[2000005];
int main()

{
	fgets(patt+1, 2000005, fin);
    fgets(txt+1, 2000005, fin);
    patt[0] = txt[0] = '.';
    p = strlen(patt) - 2;
    t = strlen(txt) - 2;
    lps[0] = -1;lps[1]=0;
	lg=0;
	//lg indica cate caractere aflate la inceputul cuvantului sunt identice cu caracterele aflate pana la i-1(inclusiv)
    for(i=2; i<=p; ++i){
        while(lg>0 and patt[i]!=patt[lg+1])
            lg=lps[lg];
        if(patt[i]==patt[lg+1])
            lg++;
        lps[i]=lg;
    }

    i = 1; j = 1;lg=0;
    //lg reprezinta cate caractere de la inceputul lui patt sunt egale cu cele aflate in txt, pana la i-1(inclusiv)
    while(i<=t and nrap<1000)
    {
       while(lg>0 and txt[i]!=patt[lg+1])
        lg=lps[lg];
       if(txt[i]==patt[lg+1])
        lg++;
       if(lg==p)
       {
           ap[++nrap]=i-p;
           lg=lps[p];
       }
     i++;
    }

    fprintf(fout, "%d\n", nrap);
    for(i=1; i<=nrap; ++i)
        fprintf(fout, "%d ", ap[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}