We present a new algorithm for subsequence matching in grammar compressed strings. Given a grammar of size n compressing a string of size N and a pattern string of size m over an alphabet of size σ, our algorithm uses O(n +(nσ)/w) space and O(n + (nσ)/w + m log N log w · occ) or O(n + (nσ)/w log w + m log N · occ) time. Here w is the word size and occ is the number of occurrences of the pattern. Our algorithm uses less space than previous algorithms and is also faster for occ = o( n/(log N)) occurrences. The algorithm uses a new data structure that allows us to efficiently find the next occurrence of a given character after a given position in a compressed string. This data structure in turn is based on a new data structure for the tree color problem, where the node colors are packed in bit strings.
展开▼
机译：我们提出了一种新的算法，用于语法压缩字符串中的子序列匹配。给定大小为n的语法在大小为σ的字母表上压缩大小为N的字符串和大小为m的模式字符串，我们的算法使用O（n +（nσ）/ w）空间和O（n +（nσ）/ w + m log N log w·occ）或O（n +（nσ）/ w log w + m log N·occ）时间。这里w是单词大小，occ是模式出现的次数。我们的算法比以前的算法使用更少的空间，并且在出现occ = o（n /（log N））时也更快。该算法使用一种新的数据结构，该结构使我们能够有效地找到压缩字符串中给定位置之后给定字符的下一次出现。该数据结构又基于用于树颜色问题的新数据结构，其中节点颜色打包在位字符串中。
展开▼
