Pagini recente » Cod sursa (job #1022785) | Cod sursa (job #2780803) | Cod sursa (job #1946682) | Cod sursa (job #2605236) | Cod sursa (job #2910771)
#include <fstream>
#include <cstring>
#define NMAX 2000000
using namespace std;
ifstream fin ("produs.in");
ofstream fout ("produs.out");
char A[NMAX+2], B[NMAX+2];
int sol[NMAX+2], nr, a, b, L;
int P[NMAX+2];
int main()
{
fin>>A+1>>B+1;
a=strlen(A+1);
b=strlen(B+1);
///calcularea lui P
P[1]=0;///p[i]=lungimea celei mai lungi secvente terminate pe poz i care este si sufix
L=0;///lungimea secvenetei dupa regula de mai sus terminata pe poz i-1 cand sunt la poz i
for(int i=2; i<=a; i++)
{
///mereu compar pe A[i] cu A[L+1] pana gasesc potrivire, altfel actualizez L-ul
while(L!=0 && A[i]!=A[L+1])
L=P[L];
///iese fie cand L=0, sau cand A[i]=A[L+1], sau ambele
///mai fac o verificare
if(A[i]==A[L+1])
L++;
P[i]=L;
}
///timpul este O(2*a) pt ca L se mareste de maxim a ori(se mareste cu 1 la fiecare pas din for)
///iar while-ul din for scade din L nostru, deci nu poate face mai mult de a pasi
///in tot for+while =a+a, deci O(a)
///utilizarea lui P pentru a rezolva cerinta
///L=cea mai lunga secventa din B terminata pe poz i care sa fie prefix a lui A
///cand L=a at stim ca am gasit sirul A in sirul B
L=0;
for(int i=1; i<=b; i++)
{
while(L!=0 && B[i]!=A[L+1])
L=P[L];
if(B[i]==A[L+1])
L++;
if(L==a)
{
nr++;
if(nr<=1000)
sol[nr]=i-a;///in prob sirul ni se cere indexat de la 0, noi am lucrat cu el indexat de la 1
L=P[L];///daca si urm poz va face potrivire nu mai am cu sa cresc L daca e deja a, asa ca fac un pas inapoi
}
}
///timpul de executie este (2*b) pe ac principiu ca mai sus, adica O(b)
///de unde rezulta complexitatea de O(a+b)
fout<<nr<<"\n";
for(int i=1; i<=min(nr, 1000); i++)
fout<<sol[i]<<" ";
return 0;
}