
	WORDS - SOLUTIE
       -----------------

by Jozef Tvarozek

It is DP.  We have word V whose occurences are we interested in. V has
letters V1,...VM
First you pre-compute table suff[i][j] = k; for i=0...M, j=a...z 
==>
suff[i][j] = k iff (if and only if; the iff sign
is standard expression....) the longest suffix of V in the word 
A=V_1...V_i
+ j (i.e. prefix of V of length i with
a character added on the end) is of length k. The whole table can be
pre-computed in 26*O(M^2) time (using
KMP).

Now we are interested in the table res[i][j]; i=0...M, j=0...k; 
res[i][j] is
the number of words of length L
containing exactly j occurences of V and whose longest suffix of V is
exactly i letters long. You initialize this
table for L = 0 and compute it for the next values of L. To compute the
values for L (we use the pre-computed
table suff) only the values for L-1 are required. This algorithm run is
horrible 26*O(N*M*K) complexity. When
I solved it on the competition - I got about 60% and I have the suff 
table
pre-computed in worse complexity and
I have made k=0 bug. If these bugs would have been repaired I would get
about 80-90%. For 100% sol you
would probably need to upgrade the suff table even more, since adding 
many
letters results in no suffix of V you
could handle them separately (you dont need to 20 times add
res[suff[i][j]][x] (len=L-1) to res[0][x](len=L),
but you would instead add 20*res[0][x] (len=L-1) to res[0][x] (len=L) 
since
20 values of suff[i][j] for j=a...z
are zero, thus you wuld require 6(for those non-zero)+1(for 20 zero 
values)
addition). The algorithm would run
in C*O(N*M*K) (c < 26). Hope you have understood it.