Cod sursa(job #1743936)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 18 august 2016 23:11:44
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.14 kb
type sir=array [1..2000005]of char;
     tablou=array [1..2000005]of longint;
var A,B:sir;
    pi,t:tablou;
    i,k,m,n,q:longint;
    f,g:text;
 
procedure prefix(A:sir;var pi:tablou);
 var i,q:longint;
  begin
   q:=0;
   pi[1]:=0;
   for i:=2 to n 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;
 
begin
 assign(f,'strmatch.in');
 assign(g,'strmatch.out');
 reset(f);
 rewrite(g);
while not eof(f) do
 begin
 while not eoln(f) do
  begin
   n:=n+1;
   read(f,A[n]);
  end;
 readln(f);
 while not eoln(f) do
   begin
    m:=m+1;
    read(f,B[m]);
   end;
end;
prefix(A,pi);
 k:=0;
 q:=0;
 for i:=1 to m 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=n then begin
                  q:=pi[n];
                  k:=k+1;
                  t[k]:=i-n;
                  end;
    end;
if k<=1000 then begin
        writeln(g,k);
        for i:=1 to k do
         write(g,t[i],' ');
         end
  else begin
      writeln(g,1000);
      for i:=1 to 1000 do
        write(g,t[i],' ');
        end;
close(f);
close(g);
end.