{
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 }