Location-Sensitive String Problems in MPC
Jacob Gilbert, MohammadTaghi Hajiaghayi, Hamed Saleh, Saeed Seddighin · 2023
A suffix tree is a trie-like data structure that stores every suffix of an input string of length n. Finding the Suffix Tree of a given string is a well-studied and classic problem. A compressed suffix tree is constructible in O(n) time using the well-known algorithm of McCreight (JACM, 1976). 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.