Cod sursa(job #423145)

Utilizator andrey932Andrei andrey932 Data 23 martie 2010 15:49:10
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.56 kb
var p,t:array[0..2000011] of char;
    k:array[0..2000011] of longint;
    r:array[0..1001] of longint;
    i,j,lp,lt,n:longint;
    s:string;
    te:text;

procedure index_kmp;
var i,j:longint;
begin
k[0]:=0; k[1]:=0;
for i:=2 to lp do
  begin
    j:=k[i-1];
    k[i]:=0;
    while (1=1) do
      begin
        if (p[j+1]=p[i]) then
          begin
            k[i]:=j+1;
            break;
          end
        else if j=0 then break;
        j:=k[j];
      end;
  end;
end;

procedure kmp;
var i,j:longint;
begin
index_kmp;
i:=1; j:=0;
while (i<=lt) do
  begin
    while (1=1) do
      begin
        if p[j+1]=t[i] then
          begin
            i:=i+1;
            j:=j+1;
            if j=lp then
              begin
                n:=n+1;
                if n<1001 then
                  r[n]:=i-lp-1;
              end;
            break;
          end
        else if j=0 then
          begin
            i:=i+1;
            break;
          end;
        j:=k[j];
      end;
  end;
end;

begin
n:=0; lp:=0; lt:=0;
assign(te,'strmatch.in'); reset(te);
while(not(eoln(te))) do
  begin
    read(te,s);
    for i:=1 to length(s) do
      p[lp+i]:=s[i];
    lp:=lp+length(s);
  end;
readln(te);
while(not(eoln(te))and not(eof(te))) do
  begin
    read(te,s);
    for i:=1 to length(s) do
      t[lt+i]:=s[i];
    lt:=lt+length(s);
  end;

close(te);
assign(te,'strmatch.out'); rewrite(te);
kmp;
writeln(te,n);
if n>1000 then n:=1000;
for i:=1 to n do write(te,r[i],' ');
close(te);
end.







end.