CLR cover
Previous problem

Problem 110: Weights of Factors

Next problem

The weight of a word on the alphabet $\{\sa{1},\sa{2}\}$ 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 $n$. In this limited alphabet, the potentially maximal weight is $2n$ and the maximal number of different weights among factors is $2n-1$.

Design a simple linear-time algorithm computing the number of different weights of non-empty factors of a word $x\in\{\sa{1},\sa{2}\}^+$.

Show that after preprocessing the word $x$ in linear time each query of the type "is there is a non-empty factor of $x$ of positive weight $k$?" can be answered in constant time. The memory space after preprocessing should be of constant size.