Cod sursa(job #276940)

Utilizator FllorynMitu Florin Danut Flloryn Data 11 martie 2009 13:46:30
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.12 kb
program pascal;
var f,g:text; z:array[1..2000000] of longint; q,k,i,m,n,j:longint;
    s,t,aux:string; x:array[1..10001] of integer;
    rez:longint;      ok:boolean;

  procedure prefix(t:string);
  begin
  m:=length(t);
  z[1]:=0;
  k:=0;
  for q:=2 to m do
   begin
   while (k>0) and (t[k+1]<>t[q]) do k:=z[k];
   if t[k+1]=t[q] then k:=k+1;
   z[q]:=k;
   end;
  end;

  PROCEDURE KMP;
  begin
  N:=LENGTH(s);
  M:=LENGTH(t);
  prefix(t);
  q:=0;
  for i:=1 to n do
    begin
    while (q>0) and (t[q+1]<>s[i]) do q:=z[q];
    if (t[q+1]=s[i]) then q:=q+1;
    if q=m then
          begin
          inc(rez);
          x[rez]:=i-m;
          if rez=1000 then ok:=true;
          q:=z[q];
          end;
    if ok then break;
    end;
  end;

  procedure citire;
  begin
  assign(f,'strmatch.in'); reset(f);
  assign(g,'strmatch.out'); rewrite(g);
  readln(f,s);
  readln(f,t);
  aux:=s; s:=t; t:=aux;
  close(f);
  end;

  procedure afisare;
  begin
  writeln(g,rez);
  for i:=1 to rez do write(g,x[i],' ');
  end;

begin
citire;
rez:=0; ok:=false;
KMP;
afisare;
close(g);
end.