Cod sursa(job #422857)

Utilizator andrey932Andrei andrey932 Data 23 martie 2010 11:44:34
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.56 kb
var a,b:array[0..2000000] of char;
    k:array[0..2000000] of longint;
    rez:array[0..1001] of longint;
    n,l1,l2,i,r:longint;
    c:char;
    t:text;

procedure index_kmp(var b:array of char;l:longint);
var i,j:longint;
begin
k[0]:=0; k[1]:=0;
for i:=2 to l do
  begin
    j:=k[i-1];
    k[i]:=0;
    repeat
      begin
     //   writeln('if ',j+1,' ',i,'   ',b[j+1],' ',b[i]);
        if b[j+1]=b[i] then
          begin
            k[i]:=j+1;
            break;
          end
        else j:=k[j];
      end;
    until j=0;
  end;
end;

procedure kmp(var a,b:array of char;l1,l2:longint);
var i,j:longint;
begin
index_kmp(b,l2);
i:=1; j:=0;
while (i<=l1) do
  begin
    if b[j+1]=a[i] then
      begin
        i:=i+1;
        j:=j+1; //au fost acceptate literele pana la pozitia j din stringul cautat
        if j=l2 then
          begin
            n:=n+1;
            if n<=1000 then rez[n]:=i-l2-1;
          end;
      end
    else if j>0 then j:=k[j]
    else i:=i+1;
  end;
end;

begin
assign(t,'strmatch.in'); reset(t);

while (not(eoln(t))) do
  begin
    read(t,c);
    l2:=l2+1;
    b[l2]:=c;
  //  write(c);
  end;    //   writeln;
readln(t);
while (not(eoln(t)) and not(eof(t))) do
  begin
    read(t,c);
    l1:=l1+1;
    a[l1]:=c;
  //  write(c);
  end;

close(t);  assign(t,'strmatch.out'); rewrite(t);
kmp(a,b,l1,l2);
//for i:=1 to l2 do writeln(i,'->',k[i]); readln;
writeln(t,n);
if n>1000 then
  for i:=1 to 1000 do write(t,rez[i],' ')
else
  for i:=1 to n do write(t,rez[i],' ');
close(t);
end.