Finding submasses in weighted strings with Fast Fourier Transform Original Research Article

We study the Submass Finding Problem: given a string s over a weighted alphabet, i.e., an alphabet image with a weight function image, we refer to a mass image as a submass of s if s has a substring whose weights sum up to M. Now, for a set of input masses image, we want to find those image which are submasses of s, and return one or all occurrences of substrings with mass image. We present efficient algorithms for both the decision and the search problem. Furthermore, our approach allows us to compute efficiently the number of different submasses of s.