TY - JOUR

T1 - Finding submasses in weighted strings with Fast Fourier Transform

AU - Bansal, N.

AU - Cieliebak, M.

AU - Lipták, Z.

PY - 2007

Y1 - 2007

N2 - We study the Submass Finding Problem: given a string s over a weighted alphabet, i.e., an alphabet S with a weight function µ : S -> N, we refer to a mass M ¿ N as a submass of s if s has a substring whose weights sum up to M. Now, for a set of input masses {M1,…,Mk}, we want to find those Mi which are submasses of s, and return one or all occurrences of substrings with mass Mi. 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.
The main idea of our algorithms is to define appropriate polynomials such that we can determine the solution for the Submass Finding Problem from the coefficients of the product of these polynomials. We obtain very efficient running times by using Fast Fourier Transform to compute this product. Our main algorithm for the decision problem runs in time O(µs log µs), where µs is the total mass of string s. Employing methods for compressing sparse polynomials, this runtime can be viewed as O(s(s) log2 s(s)) where s(s) denotes the number of different submasses of s. In this case, the runtime is independent of the size of the individual masses of characters.

AB - We study the Submass Finding Problem: given a string s over a weighted alphabet, i.e., an alphabet S with a weight function µ : S -> N, we refer to a mass M ¿ N as a submass of s if s has a substring whose weights sum up to M. Now, for a set of input masses {M1,…,Mk}, we want to find those Mi which are submasses of s, and return one or all occurrences of substrings with mass Mi. 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.
The main idea of our algorithms is to define appropriate polynomials such that we can determine the solution for the Submass Finding Problem from the coefficients of the product of these polynomials. We obtain very efficient running times by using Fast Fourier Transform to compute this product. Our main algorithm for the decision problem runs in time O(µs log µs), where µs is the total mass of string s. Employing methods for compressing sparse polynomials, this runtime can be viewed as O(s(s) log2 s(s)) where s(s) denotes the number of different submasses of s. In this case, the runtime is independent of the size of the individual masses of characters.

U2 - 10.1016/j.dam.2005.09.019

DO - 10.1016/j.dam.2005.09.019

M3 - Article

VL - 155

SP - 707

EP - 718

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 6-7

ER -