Cod sursa(job #872156)

Utilizator Buzu_Tudor_RoCont vechi Buzu_Tudor_Ro Data 5 februarie 2013 20:43:19
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.13 kb
Program p1;
var fi,fo:text; i,k,n,m,nrsol:longint;
    pattern,t:ansistring;
    z:array[0..2000001] of longint;
    sol:array[0..1001] of longint;
begin
    assign(fi,'strmatch.in'); reset(fi);
    assign(fo,'strmatch.out'); rewrite(fo);
    readln(fi,pattern); read(fi,t); nrsol:=0;
    z[1]:=0; k:=0; m:=length(pattern); n:=length(t);

    for i:=2 to m do begin
                     while (k>0) and (pattern[k+1]<>pattern[i]) do k:=z[k];
                     if pattern[k+1]=pattern[i] then k:=k+1;
                     z[i]:=k;
                     end;

    k:=0;
    for i:=1 to n do begin
                     while (k>0) and (pattern[k+1]<>t[i]) do k:=z[k];
                     if pattern[k+1]=t[i] then k:=k+1;
                     if k=m then begin
                                 k:=z[m];
                                 nrsol:=nrsol+1;
                                 if nrsol<=1000 then sol[nrsol]:=i-m;
                                 end;
                     end;

    writeln(fo,nrsol);
    if nrsol>1000 then nrsol:=1000;
    for i:=1 to nrsol do write(fo,sol[i],' ');
    close(fi); close(fo);
end.