Optimal Character Distance Sampling for Exact String Matching Through Set Cover Reformulation

Character Distance Sampling(CDS) is part of a broader class of stringmatching techniques that leverage sampling strategies. These methods provide an effective compromise between the prohibitive space requirements of offline approaches and the high computational costs of online solutions. In recent years, CDS has emerged as one of the most efficient sampling-based techniques, encoding the distances between consecutive occurrences of selected pivot characters within a string. However, its effectiveness has been validated only experimentally, and a formal theoretical foundation is still lacking to address key challenges associated with its application. Among these challenges are the optimal selection of pivot characters to enhance the sampled text representation and the handling of patterns that do not contain any pivots, which represents a worst-case scenario for CDS. In this paper, we propose an initial solution to this problem by formulating it as a variant of theSet Cover Problem, where substrings represent the elements to be covered, and characters serve as candidate sets. Specifically, we establish the theoretical connection between CDS and the Set Cover Problem, propose algorithms for constructing optimal CDS representations, and demonstrate their effectiveness in avoiding worst-case scenarios while minimizing memory usage. From our experimental results it turns out that the proposed optimization framework achieves a significant reduction in memory usage, with sampled text sizes reduced from 12.7% to 83.5%, compared to existing methods. Additionally, the optimized representation improves search speed from 55.1% to 86.2%, highlighting its practical utility in efficient substring search.