Cod sursa(job #2515766)

Utilizator biopreaOprea Bianca bioprea Data 29 decembrie 2019 15:28:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
//FILE *fin = fopen("strmatch.in", "r");
//FILE *fout = fopen("strmatch.out", "w");
ifstream fin("strmatch.in");

ofstream fout("strmatch.out");
const int DIM = 2e6 + 7;
int p,t,i,j,lps[2000005],nrap,ap[DIM],k,lg;
char patt[2000005],txt[2000005];
int main()

{
	//fgets(patt+1, 2000005, fin);
   // fgets(txt+1, 2000005, fin);
       fin.getline( patt + 1, DIM - 5 );
       fin.getline( txt + 1, DIM - 5 );
       p = strlen( patt + 1 );
       t = strlen( txt + 1 );
   // 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 )
    {
       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);
   fout<<nrap<<'\n';
   if(nrap>1000) nrap=1000;
    for(i=1; i<=nrap; ++i)
       fout<<ap[i]<<' ';
    //fclose(fin);
  //  fclose(fout);
    return 0;
}