Cod sursa(job #709445)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 8 martie 2012 09:21:02
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.35 kb
program kmp;
var f,g:text;
a:array[1..2000000] of longint;
v:array[1..1000] of longint;
sir,subsir:ansistring;
lsir,lsubsir,k,j,i,numar:longint;
bufin,bufout:array [1..65000] of byte;
procedure creare;
  begin
  k:=0; a[1]:=0;
     for i:=2 to lsubsir do
       begin
         while (k>0)  and (subsir[i]<>subsir[k+1]) do
           k:=a[k];
         if subsir[i]=subsir[k+1] then
           k:=k+1;
       a[i]:=k;
       end;
  end;
 begin
   assign(f,'strmatch.in'); reset(f);
   assign(g,'strmatch.out'); rewrite(g);
   settextbuf(f,bufin);
   settextbuf (g,bufout);
       readln(f,subsir);
       read(f,sir);
       lsir:=length(sir);
       lsubsir:=length(subsir);
       creare;
        k:=0;

        for j:=1 to lsir do
          begin
          while (k>0) and (sir[j]<>subsir[k+1]) do
               k:=a[k];

          if sir[j]=subsir[k+1] then
               k:=k+1;

          if k=lsubsir then
               begin
                  numar:=numar+1;
                  if numar<1001 then
                   v[numar]:=j-k;
                   k:=a[k];
               end;

          end;
          writeln(g,numar);
        if numar>1000 then
          for i:=1 to 1000 do
              write(g,v[i],' ')
        else
          for i:=1 to numar do
           write(g,v[i],' ');
   close(f);
   close(g);
 end.