Biotechnology Laboratory

A weighted string is defined over an alphabet Σ and a function f that assigns a weight to each character in the alphabet. Thus, we can define the weight of a string s as the sum of the weights of all characters in s.

Several problems in bioinformatics can be formalized as problems on weighted strings. One example is protein mass spectrometry, a technique that allows proteins to be identified quite efficiently. We can represent each amino acid by a distinct character, and a protein is represented by the string of characters relating to its component amino acids.

One of the applications of protein mass spectrometry is database searches. To do this the chain representing the protein is divided into subchains, the mass of each subchain is determined, and the mass list is compared with a protein database. One of the challenges for this technique is dealing with very large character strings, which may have several possible subchains. The number of subchains selected is critical to obtaining good results.

On his first day of his internship in a renowned biotechnology laboratory, Carlos was given the task of determining, for a string s, the number of distinct weights found by evaluating the weights of all non-empty subchains of consecutive characters of s.

Carlos could not think of an efficient solution for this task, but fortunately he knows the ideal group to help him.

Consider that s is made up of lowercase letters and each letter has a different weight between 1 and 26: letter a has weight 1, letter b has weight 2, and so on. Show that your team is able to help Carlos impress his supervisor in the very first week with a solution that can easily handle the largest character strings available.