Cod sursa(job #192967)

Utilizator Vlad2008Vlad VLD Vlad2008 Data 1 iunie 2008 18:45:28
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.34 kb
program Potrivirea_sirurilor;
  var a,b:array[1..2000001] of char;
      nr,n,m,k,q,i:longint;
      v,vv:array[1..2000001] of longint;
      ok:boolean;
  procedure prefix;inline;
    begin
      v[1]:=0; k:=0;
      for q:=2 to m do
         begin
           while(k>0)and(b[k+1]<>b[q]) do k:=v[k];
           if b[k+1]=b[q] then k:=k+1;
           v[q]:=k;
         end;
    end;
  procedure kmp; inline;
    begin
      k:=0; nr:=0;
  for q:=1 to n do
    begin
      while (k>0)and(a[q]<>b[k+1]) do k:=v[k];
      if a[q]=b[k+1] then k:=k+1;
      if k=m then begin inc(nr); if nr<=1000 then vv[nr]:=q-m; k:=v[k]; end;
    end;
    end;
  begin
  assign(input,'strmatch.in'); reset(input); assign(output,'strmatch.out'); rewrite(output);
  m:=0;
  while not seekeoln do begin inc(m); read(b[m]);end;
  readln;
  n:=0;
  while not seekeoln do begin inc(n); read(a[n]);end;
  if n=m then
    begin
      ok:=true;
      i:=1;
      while (i<=n)and(ok) do
        begin
          if a[i]<>b[i] then ok:=false;
          inc(i);
        end;
        if ok then begin writeln('1'); writeln(0); end
               else begin writeln('0'); end;
    end
       else
     begin
  prefix;
  kmp;
  writeln(nr);
  if nr>1000 then nr:=1000;
  for q:=1 to nr do
     write(vv[q],' '); end;
  close(input); close(output);
  end.