Cod sursa(job #1743575)

Utilizator mihaitamoglanmihai moglan mihaitamoglan Data 18 august 2016 13:45:40
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.05 kb
type sir=array [1..2000000]of char;
     tablou=array [1..2000000]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;
   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;
 i:=1;
 while (k<1000)and (i<=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;
     i:=i+1;
    end;
writeln(g,k);
for i:=1 to k do
 write(g,t[i],' ');
close(f);
close(g);
end.