Thuật toán KMP

[songohan2009]

const
  fi = 'KMP.INP';
  fo = 'KMP.OUT';

var
  f1 , f2 : text;
  n , m : longint;
  p , t : ansistring;
  kmp : array[0..1000000]of longint;

procedure open;
begin
  assign(f1 , fi);
  reset(f1);
  assign(f2 , fo);
  rewrite(f2);
end;

procedure inp;
begin
  readln(f1 , p);
  readln(f1 , t);
  close(f1);
end;

procedure process;
var
  i , k : longint;
begin
  kmp[1] := 0;
  n := length(p);
  m := length(t);

  for i := 2 to n do
    begin
      k := kmp[i-1];
      while (k > 0) and (p[k+1] <> p[i]) do
        k := kmp[k];
      if p[k+1] = p[i] then
        kmp[i] := kmp[i-1] + 1;
    end;

  k := 0;
  for i := 1 to m do
    begin
      while (k > 0) and (t[i] <> p[k+1]) do
        k := kmp[k];
      if t[i] = p[k+1] then
        begin
          inc(k);
          if k = n then
            begin
              write(f2 , i-n+1 , ' ');
              k := kmp[n];
            end;
        end;
    end;
  close(f2);
end;

begin
  open;
  inp;
  process;
end.

Code bài này em thấy sai ở test:

  p = 'ABAAA';
  t = 'ABAAAAAAAAAB';

Kết quả có 1 mà chuơng trình ra tận 4.
Đoạn code có sai ở đâu ko nhỉ? Các anh giúp em với

[technolt]

Sửa đoạn khởi tạo Compute Prefix Function như sau

      if p[k+1] = p[i] then
        k := k + 1;
      kmp[i]:=k;