Cod sursa(job #422960)

Utilizator andrey932Andrei andrey932 Data 23 martie 2010 12:58:40
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 1.5 kb
var p:array[0..1000011] of char;
    l1,l2,n,i:longint;
    k:array[0..1000011] of longint;
    t:text;
    c:char;
    x:array[0..1011] of longint;
    stop:boolean;

procedure kmp_index();
var i,j:longint;
begin
k[0]:=0; k[1]:=0;
l1:=0;
i:=1; read(t,c); p[1]:=c;
stop:=true;
while (not(eoln(t))) do
  begin
  //  write(i);
    i:=i+1;
    read(t,p[i]);
    j:=k[i-1];
    k[i]:=0;
    repeat
      if p[j+1]=p[i] then
        begin
          k[i]:=j+1;
          break;
        end
      else j:=k[j];
    until j=0;
  end;

l1:=i;
end;

procedure kmp();
var i,j:longint;
begin
l2:=0;
j:=0;
i:=1;  read(t,c);
n:=0;
stop:=false;
while(not(eof(t))and not(eoln(t))) do
  begin
    if p[j+1]=c then
      begin
        j:=j+1;
        i:=i+1;
        read(t,c);
        if j=l1 then
          begin
          j:=k[j];
            n:=n+1;
            if n<=1000 then x[n]:=i-l1-1;
          end;
      end
    else if j>0 then j:=k[j]
    else
      begin
        i:=i+1; read(t,c);
      end;
  end;
//writeln(j); readln;
//if j>0 then
  begin
   // j:=k[j];
    if (p[j+1]=c)and(j+1=l1) then
      begin
        n:=n+1;
        if n<=1000 then x[n]:=i-l1;
      end;
  end;

l2:=i;
end;


begin
assign(t,'strmatch.in'); reset(t);
kmp_index();
readln(t);
kmp();
close(t);
assign(t,'strmatch.out'); rewrite(t);
writeln(t,n);
//for i:=1 to l1 do writeln(i,'->',k[i]); readln;
if n>1000 then n:=1000;
for i:=1 to n do
  write(t,x[i],' ');
close(t);
end.