Cod sursa(job #2989415)

Utilizator Luca529Taschina Luca Luca529 Data 6 martie 2023 16:39:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b; // modelul care se cauta, textul in care se cauta
int lp[2000001], s[1001], lm, i, ns; // lungimile prefixelor, solutiile

void kmp_table()
{int im=0, ip=0; // indice pentru model, indice pentru prefix
 char c='\0';
 lp[0]=-1; // !! ca sa se avanseze in text folosind formula [*]

 while(im<=lm-1)
 {if(a[im]==c)
  {lp[im+1]=ip+1;
   ip++;
   im++;
  }
  else if(ip>0)ip=lp[ip];
  else
  {lp[im+1]=0;
   im++;
  }
  c=a[ip];
 }
}

void kmp_search()
{int it=0, im=0;

 int lt=b.size(), lm=a.size();
 while (it+im<=lt-1) // cat timp nu depasim ultimul caracter
 {if(b[it+im]==a[im]) // Caracterele se potrivesc.
  im++;                // Trecem sa comparam urmatorul caracter.
  else  // Caracterele nu se potrivesc.
  {it+=im-lp[im];   // noua pozitie in text [*]
   if(im>0)im = lp[im];     // Mergem la primul loc unde nu am comparat.
  }
  if (im==lm) // S-au potrivit toate caracterele.
  {ns++;
   if(ns<=1000)
   s[ns]=it;
  }
 }
}

int main()
{
    fin>>a>>b;
    lm=a.size();

    kmp_table();
    kmp_search();

    fout<<ns<<"\n";
    for(int i=1;i<=min(ns, 1000);i++)
    fout<<s[i]<<" ";
    return 0;
}