Cod sursa(job #1712488)

Utilizator medicinedoctoralexandru medicinedoctor Data 2 iunie 2016 22:26:56
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 0.92 kb
var m,n,i,q,w:integer;
pi:array [1..2000005] of integer;
pos:array [1..1024] of integer;
a,b:string;

procedure mp;
var i,q:integer;
begin
  pi[1]:=0; q:=0;
  for i:=2 to m do
  begin
    while ((q<>0) and (a[q+1]<>a[i])) do
      q:=pi[q];
    if (a[q+1]=a[i]) then q:=q+1;
    pi[i]:=q;
  end;
end;

procedure lire;
begin
  assign(input,'strmatch.in');
  reset(input);
  readln(a); m:=length(a);
  readln(b); n:=length(b);
  close(input);
end;

procedure ecrire;
var i:integer;
begin
  assign(output,'strmatch.out');
  rewrite(output);
  writeln(w);
  if w>1000 then w:=1000;
  for i:=1 to w do
    write(pos[i],' ');
  close(output);
end;

begin
  lire;
  q:=0; w:=0;
  mp;
  for i:=1 to n do
  begin
    while ((q<>0) and (a[q+1]<>b[i])) do
      q:=pi[q];
    if a[q+1]=b[i] then q:=q+1;
    if q=m then begin q:=pi[m]; w:=w+1; if (w<=1000) then pos[w]:=i-m; end;
  end;
  ecrire;
end.