|
Problem 110: Weights of Factors
|
|
The weight of a word on the alphabet is the
arithmetic sum of its letters.
The problem deals with the weights of all the
non-empty factors of a given word of length .
In this limited alphabet,
the potentially maximal weight is and the maximal number of different
weights among factors is .
Design a simple linear-time algorithm computing the number of different
weights of non-empty factors of a word .
Show that after preprocessing the word in linear time each query of the
type "is there is a non-empty factor of of positive weight ?" can be
answered in constant time.
The memory space after preprocessing should be of constant size.