CLR cover
Previous problem

Problem 110: Weights of Factors

Next problem

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.