Cod sursa(job #708850)

Utilizator mada0222Tomus Madalina mada0222 Data 7 martie 2012 12:36:38
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.26 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;
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);
       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.