TY - GEN

T1 - Efficient algorithms for finding submasses in weighted strings

AU - Bansal, N.

AU - Cieliebak, M.

AU - Lipták, Z.

PY - 2004

Y1 - 2004

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, decide for an input mass M whether s has a substring whose weights sum up to M. If M is indeed a submass, then we want to find
one or all occurrences of such substrings. 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 standard 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, decide for an input mass M whether s has a substring whose weights sum up to M. If M is indeed a submass, then we want to find
one or all occurrences of such substrings. 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 standard 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.1007/978-3-540-27801-6_14

DO - 10.1007/978-3-540-27801-6_14

M3 - Conference contribution

SN - 3-540-22341-X

T3 - Lecture Notes in Computer Science

SP - 194

EP - 204

BT - Combinatorial Pattern Matching (15th Annual Symposium, CPM 2004, Istanbul,Turkey, July 5-7, 2004. Proceedings)

A2 - Sahinalp, S.C.

A2 - Muthukrishnan, S.

A2 - Dogrusöz, U.

PB - Springer

CY - Berlin

ER -