Location-Sensitive String Problems in MPC

Abstract

A suffix tree is a trie-like data structure that stores every suffix of an input string of length 𝑛. Finding the Suffix Tree of a given string is a well-studied and classic problem. A compressed suffix tree is constructible in 𝑂(𝑛) time using the well-known algorithm of McCreight (JACM, 1976) [24]. Suffix trees alongside with hashing are two powerful tools in solving location-sensitive string problems. Many well-studied fundamental string problems such as String Matching, Longest Palindrome Substring (LPS), Longest Common Substring (LCS), and Longest Common Prefix (LCP) queries are location-sensitive and have linear time solutions via reductions to suffix tree. Inspired by suffix trees, we study location-sensitive string problems LCP, LPS, and LCS in the Massively Parallel Computation (MPC) model. Our algorithms extensively utilize a novel data structure for answering 𝑂(𝑛 1+𝜖 ) arbitrary LCP queries, called an LCPQ oracle, in 𝑂(1) rounds and with 𝑂e(𝑛 1+𝜖 ) total memory. Using our LCPQ oracle we are able to give the first 𝑂(1)-round, 𝑂e(𝑛) total memory algorithm in MPC for LPS and an𝑂(1)-round LCS solution using 𝑂e(𝑛 1+𝜖 ) total memory, beating previous state-of-the-art techniques for both problems. Furthermore, we give an 𝑂(1/𝜖)-round MPC algorithm for constructing suffix arrays and suffix trees utilizing our LCPQ oracle, and demonstrate reductions for LPS and LCS to suffix tree in 𝑂(1) rounds of MPC. Finally, we show that in the Adaptive Massively Parallel Computation (AMPC) model, we can build a fully-functional suffix tree for a given input string in 𝑂(1) rounds and with 𝑂e(𝑛) total memory for any constant 𝜖 > 0.