Cod sursa(job #472114)

Utilizator zseeZabolai Zsolt zsee Data 22 iulie 2010 22:29:15
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.39 kb
program str_match_;
type vektor = array[1..2000001] of char;
var rbuf : array[1..128000] of byte;
     s1,s2:vektor;
     n1,n2,i:longint;
     be,ki:text;
     m : array[1..1000] of longint;
     mn : longint;
     mtch: array[1 .. 2000001] of longint;

procedure add(const x:longint);inline;
begin
 inc(i);
 mtch[i] := x - 1;
end;

procedure gen_pattern(const b, e:longint );inline;
begin
 if b>e then exit;
 if b=e then
    add(b)
  else
    begin
      add(b);
      add(e);
      gen_pattern( ((b+e) shr 1)+1, e-1 );
      gen_pattern( b+1 , (b+e) shr 1 );
    end;
end;

procedure match( start:longint );inline;
var
    i:longint;
begin
  i := 1;
  while s1[ mtch[i]+1 ] = s2[ mtch[i] + start ] do
    begin
     inc(i);
    end;
  if i = n1 +1 then
    begin
     inc(mn);
     if mn <= 1000 then
          m[mn] := start;
    end;
end;

begin
 assign(be,'strmatch.in');
 assign(ki,'strmatch.out');
 settextbuf( be, rbuf );
 reset(be);
 rewrite(ki);
 while not eoln(be) do
   begin
     inc(n1);
     read(be,s1[n1]);
   end;
 readln(be);
 while not eoln(be) do
   begin
     inc(n2);
     read(be,s2[n2]);
   end;
 i := 0;
 gen_pattern( 1, n1 );
 s1[n1+1] := '_';
 mtch[n1+1] := n1;

 for i:=1 to n2-n1+1 do
    match(i);
 writeln(ki,mn);
 if mn > 1000 then mn := 1000;
 for i:= 1 to mn do write(ki,m[i]-1,' ');
 close(ki);
 close(be);
end.