230 lines
7.7 KiB
ObjectPascal
230 lines
7.7 KiB
ObjectPascal
{
|
|
Solution of task PREFIX
|
|
-------- -- ---- ------
|
|
Let S be a sequence of letters and let P be a set of primitives.
|
|
Denote by Suff(S,P) the set of sequences v such that the following
|
|
two conditions hold:
|
|
(1) v is a prefix of a primitive in P
|
|
(2) S=uv for some u.
|
|
|
|
(For two sequences of letters u and v we denote the concatenation of u and v
|
|
by uv.)
|
|
It is obvious that S can be composed from primitives in P iff the empty
|
|
sequence is in Suff(S,P). Moreover, S has an extension u on the right that
|
|
makes Su a composition of primitives in P iff Suff(S,P) is non-empty.
|
|
Therefore the following algorithm gives a solution to the task if DataFile
|
|
contains the sequence to be examined.
|
|
|
|
Res:=0;
|
|
S:=empty; NoS:=1;
|
|
ReadLn(DataFile,X);
|
|
Slength:=1;
|
|
While (X<>'.') And (NoS>0) Do Begin
|
|
Append X to the end of S;
|
|
Q:=Suff(S,P);
|
|
NoS:=number of elements of Q;
|
|
If the empty sequence is element of Q Then Res:=Slength;
|
|
ReadLn(DataFile,X);
|
|
Inc(Slength);
|
|
End;
|
|
WriteOut(Res);
|
|
|
|
One of the obvious problem with this algorithm is that the datafile is too
|
|
large to read into the memory (unless you know how to use the machine's
|
|
extra memory).
|
|
Fortunately, it is not necessary to read the whole sequence into memory.
|
|
Let us observe that Suff(Sx,P) for a sequence S and a letter x can be
|
|
computed from the set Suff(S,P). Indeed, the following algorithm satisfies
|
|
the requirement that if Q=Suff(S,P) holds before executing Next(Q,X)
|
|
then after the execution Q=Suff(SX,P) will hold.
|
|
|
|
Procedure Next(Q,X);
|
|
Begin
|
|
Q1:=empty;
|
|
Forall u in Q Do Begin
|
|
If ux is a prefix of some primitives in P Then
|
|
Begin
|
|
include ux in Q1;
|
|
If ux is equal to a primitive in P
|
|
Then include the empty sequence in Q1
|
|
End;
|
|
End;
|
|
Q:=Q1;
|
|
End;
|
|
|
|
In order to refine the algorithm Next we have to answer for the questions:
|
|
- Is a sequence ux a prefix of some primitive in P?
|
|
- Is a sequence u equal to a primitive in P?
|
|
|
|
Consider the following data structure for the set of primitives P.
|
|
Const
|
|
MaxN=100; (* maximum possible number of primitives *)
|
|
MaxL=20; (* maximum possible length of primitives *)
|
|
Var
|
|
P:Array[1..MaxN,1..MaxL] Of Char; (* array of primitives *)
|
|
L:Array[1..MaxN] Of Word; (* length of the primitives *)
|
|
|
|
Let us represent a sequence u which is a prefix of a primitive in P by the
|
|
pair (i,j), such that the prefix of P[i] consisting of the first j letters
|
|
of the primitive P[i] equals u, and i is the least such index for u.
|
|
Note that the empty sequence is represented by the pair (1,0).
|
|
|
|
We can pre-process the set of primitives to build a transition table T:
|
|
|
|
T[i,j,x] is 0 if there is no primitive in P with prefix P[i][1..j]x,
|
|
otherwise the least index k such that P[i][1..j]x is a prefix of P[k].
|
|
(P[i][1..j] denotes the sequence of letters consisting of the first j
|
|
elements of the primitive P[i].)
|
|
|
|
In other words, if a sequence u is represented by the pair (i,j) then the
|
|
sequence ux is a prefix of a primitive in P iff T[i,j,x]>0, and in this case
|
|
ux is a prefix of P[T[i,j,x]] and is represented by the pair (T[i,j,x],j+1).
|
|
The procedure BuildTable computes the transition table T and builds the array
|
|
Full as well. Full[i,j] is true iff the sequence represented by (i,j) is equal
|
|
to a primitive in P.
|
|
We can easily implement the algorithm Next(Q,X) using the arrays T and Full.
|
|
|
|
}
|
|
Program Prefix;
|
|
Const
|
|
MaxN=100; { maximum possible number of primitives }
|
|
MaxL=20; { maximum possible length of primitives }
|
|
Var
|
|
DataFile:Text; { file for the sequence to be examined }
|
|
P:Array[1..MaxN,1..MaxL] Of Char; { array of primitives }
|
|
L:Array[1..MaxN] Of Word; { length of the primitives }
|
|
T:Array[1..MaxN,0..MaxL,'A'..'Z'] Of Byte; { transition table }
|
|
N, { number of primitives }
|
|
ML:Word; { max of the length of the primitives }
|
|
Res:Longint; { length of the longest prefix }
|
|
Full:Array[1..MaxN,1..MaxL] Of Boolean;
|
|
|
|
Type
|
|
State=Array[1..MaxL+1] Of Record
|
|
i,j:Byte;
|
|
End;
|
|
Procedure Init;
|
|
Var M,i,j:Word;
|
|
InFile:Text;
|
|
Begin
|
|
Assign(InFile,'input.txt'); Reset(InFile);
|
|
ReadLn(InFile,N);
|
|
ML:=0;
|
|
For i:=1 To N Do Begin
|
|
ReadLn(InFile,L[i]);
|
|
If L[i]>ML Then ML:=L[i];
|
|
For j:=1 To L[i] Do Read(InFile,P[i][j]);
|
|
ReadLn(InFile);
|
|
End;
|
|
Close(InFile);
|
|
Assign(DataFile,'data.txt'); Reset(DataFile);
|
|
End;
|
|
|
|
Procedure BuildTable;
|
|
{Global input variables: N, ML, P }
|
|
{Global output variables: T, Full }
|
|
Var
|
|
i,i1,j,k:Word;
|
|
X:Char;
|
|
Begin
|
|
For i:=1 To N Do {initialize the array Full}
|
|
For j:=1 To ML Do Full[i,j]:=False;
|
|
For i:=1 To N Do { compute T[i,0,x] }
|
|
For X:='A' To 'Z' Do Begin
|
|
k:=1;
|
|
While (k<=N) And (P[k][1]<>X) Do Inc(k);
|
|
If (k<=N) Then Begin
|
|
T[i,0,X]:=k;
|
|
Full[k,1]:=Full[k,1] Or (L[i]=1) And (P[i][1]=X);
|
|
End Else
|
|
T[i,0,X]:=0;
|
|
End;
|
|
For j:=1 To ML Do Begin
|
|
For i:=1 To N Do Begin
|
|
For X:='A' To 'Z' Do Begin { compute T[i,j,X] }
|
|
If j>L[i] Then Begin
|
|
T[i,j,X]:=0;
|
|
End Else Begin
|
|
i1:=T[i,j-1,P[i][j]];
|
|
k:=1;
|
|
While (k<=N) And
|
|
Not ((j+1<=L[k]) And (P[k][j+1]=X) And (i1=T[k,j-1,P[k][j]]))
|
|
Do Inc(k);
|
|
If (k<=N) Then Begin
|
|
T[i,j,X]:=k;
|
|
Full[k,j+1]:=Full[k,j+1] Or (L[i]=j+1);
|
|
End Else
|
|
T[i,j,X]:=0;
|
|
End;
|
|
End {for 'A'..'Z'};
|
|
End {for i};
|
|
End {for j};
|
|
End {BuildTable};
|
|
|
|
Procedure Next(Var NoS:Word; Var Q:State; X:Char; Var Complete:Boolean);
|
|
{Input: NoS is the number of prefixes in Suff(S,P),
|
|
(Q[1].i,Q[1].j),...,(Q[NoS].i,Q[NoS].j) are the representatives of
|
|
the prefixes in Suff(S,P),
|
|
X is the actual element of the sequence to be examined.
|
|
Output:NoS is the number of prefixes in Suff(SX,P),
|
|
(Q[1].i,Q[1].j),...,(Q[NoS].i,Q[NoS].j) are the representatives of
|
|
the prefixes in Suff(SX,P),
|
|
Complete is True iff the empty sequence is in Q.
|
|
}
|
|
Var i,j,ii,newi,newj:word;
|
|
Begin
|
|
ii:=0; Complete:= False;
|
|
For i:=1 To NoS Do Begin { compute next state }
|
|
newi:=T[Q[i].i,Q[i].j,X]; newj:=Q[i].j+1;
|
|
If newi>0 Then Begin
|
|
Inc(ii);
|
|
Q[ii].i:=newi; Q[ii].j:=newj;
|
|
Complete:=Complete Or Full[newi,newj];
|
|
End;
|
|
End;
|
|
If Complete Then Begin
|
|
Inc(ii); Q[ii].i:=1;Q[ii].j:=0; {include the empty string}
|
|
End;
|
|
NoS:=ii;
|
|
End {Next};
|
|
|
|
Procedure Process;
|
|
{Global input variables: DataFile }
|
|
{Global output variables: Res }
|
|
Var
|
|
X:Char; { the actual element of the sequence }
|
|
Q:State; { set of prefixes of primitives that are
|
|
suffixes of the sequence red so far }
|
|
NoS:Word; { number of the elements of Q }
|
|
Slength:Longint; { length of the sequence red so far }
|
|
Complete:Boolean;
|
|
Begin
|
|
NoS:=1; Q[1].i:=1; Q[1].j:=0; { initialize Q }
|
|
Res:=0; Slength:=1;
|
|
ReadLn(DataFile,X);
|
|
While (X<>'.') And (NoS>0) Do Begin
|
|
Next(NoS,Q,X,Complete);
|
|
If Complete Then Res:=Slength;
|
|
ReadLn(DataFile,X);
|
|
Inc(Slength);
|
|
End {While};
|
|
Close(DataFile);
|
|
End {Process};
|
|
|
|
Procedure WriteOut(Res:Longint);
|
|
Var OutFile:Text;
|
|
Begin
|
|
Assign(OutFile,'output.txt'); Rewrite(OutFile);
|
|
WriteLn(OutFile,Res);
|
|
Close(OutFile);
|
|
End;
|
|
|
|
Begin
|
|
Init;
|
|
BuildTable;
|
|
Process;
|
|
WriteOut(Res);
|
|
End.
|
|
|
|
{ Scientific Committee IOI'96 }
|