Xét dãy số nguyên A=(a1,a2,....,an) . Dãy con các phần tử liên tiếp nhau B(ai,ai+1,...,aj)
được gọi là tiền tố của A nếu ai=a1,ai+1=a2,....,aj=aj-i+1 ( i>1) .
vd với dãy A=(5,3,5,5,3,4,5,3,5,5,3,6)
Dãy số P=(p1,...,pn) gọi là hàm tiền tố của A nếu Pi là độ dài dãy tiền tố dài nhất kết thúc bởi phần tử ai-1 . (p1=0)
Vói vd trên ta có P=(0,0,0,1,1,2,0,1,2,3,4,5)
Yêu cầu : Cho n và dãy số A . Hãy xác định hàm tiền tố P
Free.inp
12
5 3 5 5 3 4 5 3 5 5 3 6

Free.out

0 0 0 1 1 2 0 1 2 3 4 5

Code:


Const fi='tiento.inp'; fo='tiento.out';
 Var n:Longint;
    p,A:array[1..1000000] Of Longint;
    f,g:text;
Procedure doctep;
 Var i,j:Longint;
  Begin
  Assign(f,fi);
  Reset(f);
  Readln(f,n);
  For i:=1 to n do
    Read(f,a[i]);
  Close(f);
  Assign(g,fo);
  Rewrite(G);
  End;
Procedure xuly;
 Var i,j:Integer;
  Begin
  Fillchar(p,sizeof(p),0);
  i:=3;j:=0;
    While i<=n do
    Begin
      If a[i-1]=a[j+1] then begin p[i]:=j+1; inc(i); inc(j) End
      Else If j > 0 then j:=p[j]
      else begin p[i]:=0; inc(i); End;
    End;
  End;
Procedure xuat;
 Var i,j:Integer;
  Begin
  For i:=1 to n do
    Write(g,p[i]:3);
  End;
Begin
 doctep;
 xuly;
 xuat;
 Close(g);
End.


Link : [You must be registered and logged in to see this link.]