Cod sursa(job #423022)

Utilizator andrey932Andrei andrey932 Data 23 martie 2010 14:00:37
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1.39 kb
var p,t:array[0..2000001] of char;
    i,j,l1,l2,n:longint;
    k:array[0..2000001] of longint;
    rez:array[0..1011] of longint;
    te:text;


procedure kmp_index(var p:array of char; var l:longint);
var i,j:longint;
begin
k[0]:=0; k[1]:=0;
i:=1; read(te,p[i]);
while(not(eoln(te))) do
  begin
    i:=i+1; read(te,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
        begin
          if j=0 then break;
          j:=k[j];
        end;
    until 1=2;
  end;
l:=i;
end;

procedure kmp_search(var p,t:array of char;l1,l2:longint);
var i,j:longint;
begin
if l1=l2 then
  begin
    n:=1;
    rez[1]:=0;
    exit;
  end;
i:=1; j:=0;
while (i<=l2) do
  begin
    if t[i]=p[j+1] then
      begin
        j:=j+1;
        i:=i+1;
        if j=l1 then
          begin
            n:=n+1;
            if n<=1000 then rez[n]:=i-l1-1;
          end;
      end
        else if j>0 then j:=k[j]
        else i:=i+1;
  end;
end;

begin
assign(te,'strmatch.in'); reset(te);
kmp_index(p,l1);
readln(te);
while(not(eoln(te))and not(eof(te))) do
  begin
    l2:=l2+1;
    read(te,t[l2]);
  end;
close(te);

assign(te,'strmatch.out'); rewrite(te);
kmp_search(p,t,l1,l2);
writeln(te,n);
if n>1000 then n:=1000;
for i:=1 to n do  write(te,rez[i],' ');
close(te);
end.