Cod sursa(job #843359)

Utilizator RusuAlexeiRusu Alexei RusuAlexei Data 27 decembrie 2012 21:07:17
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.23 kb
program knutt_morris_pratt;
  var f1,f2:text;
      s1:array [0..2000000] of char;
      s2:array [1..2000000] of char;
      prefix1,prefix2:array [0..2000000] of longint;
      i,j,k,l:longint;
      rez:array [1..1000] of longint;
      bufin,bufout:array [1..100000] of char;
begin
  assign(f1,'strmatch.in');
  reset(f1);
  assign(f2,'strmatch.out');
  rewrite(f2);
  settextbuf(f1,bufin);
  settextbuf(f2,bufout);
  readln(f1,s1);
  readln(f1,s2);
  i:=1;
  while s1[i] in['A'..'Z','a'..'z','0'..'9'] do
    begin
      j:=prefix1[i-1];
      while (j>0) and (s1[i]<>s1[j]) do j:=prefix1[j-1];
      if s1[i]=s1[j] then inc(j);
      prefix1[i]:=j;
      inc(i);
    end;
  l:=i;
  i:=1;
  while s2[i] in ['A'..'Z','a'..'z','0'..'9'] do
    begin
      j:=prefix2[i-1];
      while (j>0) and (s2[i]<>s1[j]) do j:=prefix1[j-1];
      if s2[i]=s1[j] then inc(j);
      prefix2[i]:=j;
      if j=l then
               begin
                 inc(k);
                 if k<=1000 then rez[k]:=i-l;
               end;
      inc(i);
    end;
  writeln(f2,k);
  if k<1000 then for i:=1 to k do write(f2,rez[i],' ')
            else for i:=1 to 1000 do write(f2,rez[i],' ');
  close(f1);
  close(f2);
end.