کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435341 | 689895 | 2016 | 8 صفحه PDF | دانلود رایگان |
In this paper we extend several well-known document listing problems to the case when documents contain a substring that approximately matches the query pattern. We study the scenario when the query string can contain a wildcard symbol that matches any alphabet symbol; all documents that match a query pattern with one wildcard must be enumerated. We describe a linear space data structure that reports all documents containing a substring P in O(|P|+σlogloglogn+docc) time, where σ is the alphabet size and docc is the number of listed documents. We also describe a succinct solution for this problem, as well as a solution for an extension of this problem. Furthermore our approach enables us to obtain an O(nσ)O(nσ)-space data structure that enumerates all documents containing both a pattern P1P1 and a pattern P2P2 in the special case when P1P1 and P2P2 differ in one symbol.
Journal: Theoretical Computer Science - Volume 635, 4 July 2016, Pages 94–101