Efficient Online String Matching Based on Characters Distance Text Sampling

Arianna Pavone; Francesco Pio Marino; Simone Faro

REVIEW 5 major objections 6 minor 21 references

Efficient Online String Matching Based on Characters Distance Text Sampling

T0 review · 5 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper presents a character-distance sampling method for online string matching that, when every consecutive pivot gap is below block size $k$, is lossless: searching the sampled distance sequence finds every occurrence while using…

desk verdict A genuinely novel distance-sampling idea, but the current preprint has load-bearing off-by-one bugs in position reconstruction and a broken Search-0 routine; not correct as written. read the letter →

arxiv 1908.05930 v1 pith:A5I764B5 submitted 2019-08-16 cs.DS

Simone Faro , Arianna Pavone , Francesco Pio Marino This is my paper · ORCID

classification cs.DS MSC 68W32

keywords stringmatchingsampledcharacterdistancesamplingalphabetreductiontextpartialindexonlinesearchpivot

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper presents a sampled string-matching algorithm that preprocesses a text by recording, for one chosen pivot character, the position of each pivot occurrence modulo a block size $k$, plus a small mapping table. During search, it reconstructs the distances between consecutive pivot occurrences and looks for the distance sequence of the pattern in that sampled sequence; every reported candidate is then verified in the original text. The paper argues that under the condition that every pivot-to-pivot distance is shorter than $k$, this filter is lossless, so no occurrence is missed. It claims linear worst-case $O(n)$ and optimal average-case $O(n \log_\sigma m / m)$ complexity when the underlying search routine has those properties, and reports 2.8–11% extra space, sublinear practical behaviour, and speedups over plain online search of up to about 9 times. The approach is aimed at large texts with wide alphabets, such as natural language, where a frequent pivot character keeps distances below $k$.

What carries the argument

The load-bearing mechanism is the pair $(\dot{y}, \tau)$: $\dot{y}$ stores each pivot occurrence's position modulo $k$ (one byte when $k=256$), and $\tau$ stores, for each block of $k$ text characters, the index of the last pivot occurrence in that block. Lemma 2 and Corollary 2 supply the reconstruction formula (6), which recovers every consecutive-pivot distance from two consecutive $\dot{y}$ values exactly when that distance is $< k$. This identity is what makes the sampled text a lossless filter rather than a heuristic: it guarantees that a matching distance sequence in the sampled text corresponds to a genuine pattern alignment, and it gives the constant-time position lookup used during verification.

What would settle it

Set $k=3$, choose 'a' as the pivot, and run the algorithm on pattern $x=\texttt{abbba}$ (a at positions 1 and 5, true gap 4) and text $y=\texttt{abbbab}$ (a at positions 1 and 5). The pattern's sampled distance is 4, while relation (6) reconstructs the text gap as $(5 \bmod 3) - (1 \bmod 3) = 1$, so the search reports no candidate and misses the occurrence at position 1; observing that miss on this input shows the bounded-gap condition is essential to the lossless-filter claim.

Watch

Extended reading notes

Core claim

The paper's central object is the characters-distance sampled sequence: if the pivot character $c$ occurs at positions $\delta(1), \delta(2), \ldots, \delta(n_c)$, the sampled text is the sequence of gaps $\Delta(i) = \delta(i+1) - \delta(i)$. Since storing every full position would be costly, the algorithm stores only the $k$-bounded positions $\dot{y}[i] = \delta(i) \bmod k$ together with a block table $\tau$, and reconstructs each gap on the fly by the identity $\Delta(i) = \dot{y}[i+1] - \dot{y}[i]$ when $\dot{y}[i+1] > \dot{y}[i]$, and $\Delta(i) = \dot{y}[i+1] + k - \dot{y}[i]$ otherwise. The paper proves this reconstruction is exact whenever every consecutive pivot gap in the text is strictly less than $k$, and that the resulting filter never discards a true occurrence. It then searches the reconstructed distance sequence for the pattern's distance sequence and verifies each candidate in the original text, claiming that the whole procedure inherits linear worst-case and optimal average-case bounds from the underlying string-matching routine.

Load-bearing premise

The distance filter is exact only when every distance between two consecutive pivot characters in the text is strictly less than the block size $k$; if a pivot gap reaches or exceeds $k$, relation (6) wraps modulo $k$ and can reconstruct the wrong distance, causing valid matches to be missed.

Editorial extensions

If this is right

Choosing the most frequent character as pivot gives the shortest sampled text (one byte per pivot occurrence), about 11% of text size; choosing a rank-20 pivot lowers this to about 2.8%.
If the underlying search routine is linear in the worst case, the sampled search inherits the same $O(n)$ bound; if the routine is optimal on average, the sampled search inherits $O(n \log_\sigma m / m)$ for patterns up to a few hundred characters when $k=256$.
On English text the measured search times are 32% below plain Horspool for 2-character patterns and 91% below for 256-character patterns, with preprocessing faster than the earlier occurrence-sampling approach.
Preprocessing time is lower than the earlier occurrence-sampling method by 15–50%, mainly because the new sampled structure is smaller.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the same $(\dot{y}, \tau)$ structure gives near-constant recovery of pivot positions, so it could be promoted to a lightweight sparse index that counts or locates pivot-anchored matches without scanning the text.
Editorial inference: an adaptive block size chosen after measuring the pivot's maximum gap would remove the main correctness restriction while keeping byte-level storage only when gaps are actually small.
Editorial inference: a practical implementation should detect any text gap that reaches $k$ during preprocessing and fall back to a larger $k$ or to the zero- and one-pivot search strategies; the paper does not analyze such a safeguard.
Editorial inference: the approach is naturally suited to wide alphabets; on low-entropy alphabets such as DNA the pivot occurs too often, so false-positive verification would dominate, a limitation the paper itself states.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The distance-sampling idea is genuinely new, but the current preprint is not correct as written: the position reconstruction in Get-Position fails for pivot occurrences exactly on block boundaries, and Search-0's loop is broken. Those are load-bearing, not cosmetic.

What's new and good: the scheme samples distances between consecutive occurrences of a pivot character, storing positions modulo k plus a block-mapping table. That's not in Claude et al.'s alphabet sampling. The space figures (2.8–11% vs 14.8%) are credible, and the experiments on a 5MB English text show real speedups over Horspool and Ots. The three search cases are a sensible organization.

Now the soft spots. Corollary 1's formula δ(j) = (τ[b]−1)k + ˙y[j] fails when δ(j) mod k = 0. Since ˙y[j] ∈ {0,...,k−1}, a pivot at position qk gives residue 0 and the formula returns (q−1)k. The stress-test example is correct: k=5, pivot at position 5 returns 0. Every Search-0/1/2+ call to Get-Position is then wrong at those occurrences.

Search-0's pseudocode has a separate bug: the loop starts at i=2, so δ1 is never computed and the text prefix before the first pivot is never searched. Search-2+ has an off-by-one in verification: it uses y[δ_i − α] instead of δ_i − α + 1.

The theory is also shaky. Lemma 2's formula has a sign error (τ[a]−τ[b] should be τ[b]−τ[a]). Theorem 3's O(n) worst case rests on an unspecified KMP-style verification that remembers already-checked positions, with no details. The average-case optimality claims are conditional on assumptions (k≥σ, Δ(i)

Credit where due: the sampling concept is a real new technique, and the experimental methodology is standard for the area. The flaws are specific and likely fixable.

Verdict: not acceptable as is. I'd still send it to a serious referee, because the idea deserves a proper vetting and the errors are repairable. I wouldn't cite it in its current form.

Referee Report

5 major / 6 minor

Summary. The paper proposes a new sampled string matching algorithm based on sampling the distances between consecutive occurrences of a chosen pivot character. The text is divided into blocks of size k; the sampled sequence stores the position of each pivot occurrence modulo k, and a block-mapping table τ supports reconstruction of the original pivot positions. For patterns containing the pivot at least twice, the algorithm searches for the sampled pattern (the sequence of distances between consecutive pivots) in the sampled text, then verifies candidate positions in the original text. The paper claims O(n) worst-case and O(n log_σ m / m) average-case time under suitable conditions, while using 2.8%–11% of the text size as extra space, and reports experiments showing speedups over the Ots algorithm of Claude et al.

Significance. The characters-distance sampling idea is simple and potentially useful: it offers a very compact partial index and the experiments indicate practical speedups on English text, especially for short patterns. The asymptotic claims, if established, would be a nice complement to existing sampled string matching results. However, the manuscript contains several load-bearing correctness errors in the core reconstruction formula and in the Search-0 pseudocode, as well as a false lemma and an unproven worst-case theorem, so the current version cannot be accepted as a correct and complete algorithm.

major comments (5)

[§3.1, Corollary 1 and Fig. 1] The reconstruction formula δ(j) = (τ[b] − 1)k + ˙y[j] is incorrect for pivot occurrences whose position is a multiple of k, because in that case ˙y[j] = 0 and the formula returns (τ[b] − 1)k instead of τ[b]k. For example, with k = 5 and δ(j) = 5, the formula returns 0. Since Get-Position is used by all three search procedures to determine the verification offset, this can cause valid occurrences to be missed or spurious verifications to be performed, invalidating the lossless-filter claim as written. The fix is to store residues in {1, . . . , k} or to special-case the zero residue.
[§3.3, Search-0 (Fig. 5)] The main loop of Search-0 begins at i = 2 and δ1 is never initialized, so the interval before the first pivot occurrence is never searched; any occurrence of x in y[1..δ(1) − 1] is missed. The loop header 'for i≤2 to nc' also contains a typo. The procedure must either start at i = 1 after computing δ1 or handle the first interval separately.
[§3.1, Lemma 2] Lemma 2 has a sign error: from Corollary 1 the correct difference is ˙y[i+1] + (τ[b] − τ[a])k − ˙y[i], not ˙y[i+1] + (τ[a] − τ[b])k − ˙y[i]. The stated formula gives wrong values when the two pivots are in different blocks; for example, with k = 5, positions 1 and 7 give −4 instead of 6. Although Corollary 2 is correct and is what the search uses, the lemma as printed is false and should be corrected.
[§3.3, Theorem 3] The proof of the O(n) worst-case bound is not supplied. It asserts that a KMP-style Verify can 'remember all positions of the text which have already been verified,' but no such mechanism is defined, and the preceding line admits that the naive bound is O(nc·m). Since the number of candidate matches can be Θ(nc), the claimed O(n) worst case needs a precise amortized argument or a different verification strategy.
[§3.2, Corollary 2 and Theorem 3] The correctness of the distance filter depends on relation (6), which is derived under the assumption Δ(i) < k for all consecutive pivot occurrences in the text. The paper states only that the pivot rank 'must be chosen' to satisfy this condition and does not guarantee it for arbitrary inputs; the complexity theorems also do not state this condition explicitly. Please clarify the exact set of inputs for which the algorithm is correct, or extend the method to handle wrap-around distances.

minor comments (6)

[§3.1, Example 4] The first distance is incorrectly computed as δ(1) − δ(0) = 3 − 1 = 2; with the stated text δ(1) = 1 and the correct expression is δ(2) − δ(1) = 3 − 1 = 2.
[Fig. 4 and Fig. 6] Verify's loop tests x[i] against y[s+i], which implies s is a zero-based offset, yet Search-1 passes a one-based start (δ_{i−1} − α + 1) and Search-2 passes δ_i − α; this indexing convention should be made consistent.
[§3.3, references] In §3.3 the BDM algorithm is cited as [12], but reference [12] is Horspool's algorithm; the optimal-average-case citation should be to [6].
[§4.1, Figure 8] The text refers to 'Table 8' when discussing the space-consumption figure; it should be Figure 8.
[Conclusion] The conclusion says the algorithm 'may require only 5% of additional extra space,' while the abstract reports 11% to 2.8%; these numbers should be harmonized.
[Pseudocode] Several pseudocode typos remain: 'for i≤2' should be 'for i←2' in Figs. 5 and 6, and line 10 of Fig. 6 uses the undefined symbol 'pi−1'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: complexity results are conditional on the underlying algorithm and the sampled representations are independently defined.

full rationale

The paper's derivation chain is self-contained rather than circular. The sampled sequences are introduced by explicit definitions: ˙y records pivot positions modulo k (Definition 1) and ¯y records consecutive pivot distances (Definition 2). The reconstruction formulas are derived from these definitions and from the mapping table τ, which is independently defined by equation (3). In particular, Corollary 1 and Lemma 2 derive position and distance reconstruction from the definitions, and Corollary 2 (equation (6)) is a specialization under the stated condition Δ(i) < k. No fitted quantity is renamed as a prediction: the measured speedups and space consumption in Section 4 are reported experimental observations, not outputs derived from tuned parameters. The theoretical claims in Theorems 1-3 are explicitly conditional: they assume an underlying linear or optimal-average string matching algorithm and then bound the added overhead from sampling, verification, and table scanning. This is a legitimate complexity preservation argument, not an equivalence of input and output. There is no load-bearing self-citation: the authors' own prior work appears only as experimental tooling or comparative baselines, not as the source of the main correctness or complexity claims. The acknowledged limitation in Section 5 (poor efficiency on small alphabets) and the residue-0 issue in the absolute-position reconstruction formula of Corollary 1 are correctness or scope concerns, not evidence that the derivation reduces to its inputs. Accordingly, the circularity score is 0.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The algorithm introduces no new physical or mathematical entities; the sampled sequences, the block mapping table, and the pivot selection are algorithmic devices. The main load-bearing assumptions are the random-text model, the Delta(i) < k bound, and the existence of an optimal underlying search algorithm.

free parameters (2)

k (block size / position modulus) = 256 in practice; integer variable in the paper
k controls the size of the sampled text, the validity of the reconstruction formula (6), and the assumption Delta(i) < k. It is chosen by the user, not fitted to optimize the reported results, but it is a free design parameter.
r (rank of the pivot character) = varies from 1 to 20 in experiments
The pivot character is selected by frequency rank from the text. The choice determines nc (sampled text length), space usage, and filtering power. The paper requires r to be such that Delta(i) < k, making it a data-dependent parameter.

assumptions (4)

domain assumption Characters in the text are equiprobable and independent (random text model).
Used in Theorems 1-3 to compute expected number of pivot occurrences E(nc) = n/sigma and to invoke the optimal average-case bound O(n log_sigma m / m). This is a standard but strong assumption that rarely holds in natural language.
domain assumption The chosen pivot satisfies Delta(i) < k for every consecutive pair of pivot occurrences in the text and in the pattern.
Corollary 2 and the preprocessing section require this to avoid wrap-around in the distance reconstruction. The paper states this for the text pivot (Section 3.2) but the pattern is not explicitly guaranteed to satisfy it, limiting the method to patterns of length below k.
domain assumption The underlying online string matching algorithm used on the sampled text has optimal worst-case and average-case complexity.
The framework proofs transfer complexity bounds from the underlying algorithm (e.g., KMP for worst case, BDM for average case). The experimental implementation uses Horspool, which is not proven optimal, so the experimental results do not directly validate the theoretical bounds.
standard math Yao's lower bound Theta(n log_sigma m / m) for average-case online string matching is accepted as the optimal benchmark.
The paper cites [21] and uses this bound to define 'optimal average-time complexity'. This is a standard result in the string matching literature.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Online String Matching Based on Characters Distance Text Sampling." pith.science (2026). https://pith.science/paper/A5I764B5

@misc{pith2026190805930,
  author       = {Pith},
  title        = {Pith review of: Efficient Online String Matching Based on Characters Distance Text Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A5I764B5}},
  note         = {Machine review of arXiv:1908.05930}
}

read the original abstract

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. Sampled string matching is an efficient approach recently introduced in order to overcome the prohibitive space requirements of an index construction, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. In this paper we present a new algorithm for the sampled string matching problem, based on a characters distance sampling approach. The main idea is to sample the distances between consecutive occurrences of a given pivot character and then to search online the sampled data for any occurrence of the sampled pattern, before verifying the original text. From a theoretical point of view we prove that, under suitable conditions, our solution can achieve both linear worst-case time complexity and optimal average-time complexity. From a practical point of view it turns out that our solution shows a sub-linear behaviour in practice and speeds up online searching by a factor of up to 9, using limited additional space whose amount goes from 11% to 2.8% of the text size, with a gain up to 50% if compared with previous solutions.

Figures

Figures reproduced from arXiv: 1908.05930 by the authors.

**Figure 1.** (On the left) The pseudocode of procedure Get-Position which computes the index of the block corresponding the i-th occurrence of the pivot character in y. (On the right) The pseudocode of procedure Compute-Character-Distance-Sampling which computes, on the flight from ˙y, the Characters Distance sampled version of y. Lemma 2. Let y be a text of length n, let c ∈ Σ be the pivot character and assume c occurs nc times… view at source ↗

**Figure 2.** (On the left) The pseudocode of procedure Compute-Distance-Sampling for the construction of the character distance sampling version of a text y. (On the right) The pseudocode of procedure Compute-Position-Sampling for the construction of the character position sampling version of a text y [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** reports the maximum and average distances between two consecutive occurrences, computed for the most frequent characters in a natural language text. Observe that the first 6 most frequent characters follow the constraint on the maximum distance. As a consequence the choice of the pivot character directly influences the additional memory used for storing the sampled text (the larger is the rank of the pivot character… view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: The pseudocode of procedure Verify for testing the occurrence of a pattern x, of length m, in a text y, of length n, starting at position s. 3.3 The Searching Phase Let x be an input pattern of length m and let c ∈ Σ be the pivot character. Let mc be the number of occu…

**Figure 5.** Figure 5: The pseudocode of procedure Search-0 for the sampled string matching problem, when the pivot character does not occur in the input pattern x. the original text which do not contain the pivot character. Specifically such substrings are identified in the original text b…

**Figure 6.** Figure 6: shows the pseudocode of the algorithm which searches for all occurrences of a pattern x, when the pivot character c occurs only once in it. Specifically, let α be the unique position in x which contains the pivot character (line 3), i.e. we assume that x[α] = c and x[…

**Figure 7.** Figure 7: The pseudocode of procedure Search-2 for the sampled string matching problem, when the pivot character occurs more than ones in the input pattern x. The following theorem proves that procedure Search-2 achieves optimal worst-case and average-case time complexity. Theo…

**Figure 8.** Figure 8: Space consumption of the text sampled algorithms. All values are in KB. On the top: memory space required by the new algorithm, for different pivot characters with rank ranging from 1 to 20. On the bottom: memory space required by the Ots algorithm, for different sets …

**Figure 9.** Figure 9: Preprocessing times of the text sampled algorithms. Running times are expressed in thousands of seconds. The x axis represents the rank of the pivot character in the case of the new algorithm, while represents the number of removed characters in the case of previous a…

**Figure 10.** Figure 10: Running times of the text sampling algorithms in the case of small patterns (2 ≤ m ≤ 16). The dashed red line represent the running time of the original Horspool algorithm. Running times (in the y axis) are represented in thousands of seconds. The x axis represents th…

**Figure 11.** Figure 11: Running times of the text sampling algorithms in the case of long patterns (32 ≤ m ≤ 256). The dashed red line represent the running time of the original Horspool algorithm. Running times (in the y axis) are represented in thousands of seconds. The x axis represents t…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Apostolico, The myriad virtues of suﬃx trees, in: A

A. Apostolico, The myriad virtues of suﬃx trees, in: A. Apo stolico, Z. Galil (Eds.), Combinatorial Algorithms on Words, Vol. 12 of NATO Advanced Science Institutes, Series F, Springer-Verlag, pp. 85–96 (1985)

work page 1985
[2]

Boyer, J.S

R.S. Boyer, J.S. Moore. A fast string searching algorithm . Commun. ACM 20(10), 762-772 (1977)

work page 1977
[3]

Cantone, S

D. Cantone, S. Faro, E. Giaquinta: Adapting Boyer-Moore- like Algorithms for Searching Huﬀman Encoded Texts. Int. J. Found. Comput. Sci. 23(2), pp. 343–356 (2012)

work page 2012
[4]

Cantone, S

D. Cantone, S. Faro, A. Pavone: Speeding Up String Matchin g by Weak Factor Recognition. Stringology 2017, pp. 42–50 (2017)

work page 2017
[5]

Claude, G

F. Claude, G. Navarro, H. Peltola, L. Salmela, J. Tarhio, S tring matching with alphabet sampling, Journal of Discrete Algorithms, vol. 11 , pp. 37–50 (2012)

work page 2012
[6]

Crochemore, A

M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. L ecroq, W. Plandowski, W. Rytter, Speeding up two string-matching algorithms, Alg orithmica 12 (4), pp. 247–267 (1994)

work page 1994
[7]

45 (2 ), pp

S Faro, T Lecroq, The Exact Online String Matching Problem : a Review of the Most Recent Results, ACM Computing Surveys (CSUR) vol. 45 (2 ), pp. 13 (2013)

work page 2013
[8]

S. Faro, T. Lecroq, S. Borz ` ı, S. Di Mauro, and A. Maggio. Th e String Matching Algorithms Research Tool. In Proc. of Stringology , pages 99–111, 2016

work page 2016

Show all 21 references

[9]

Ferragina, G

P. Ferragina, G. Manzini. Indexing compressed text. Jour nal of the ACM, 52 (4), pp. 552–581, 2005

2005
[10]

Fredriksson and S

K. Fredriksson and S. Grabowski, A general compression a lgorithm that supports fast searching, Information Processing Letters, vol. 100 ( 6), pp. 226–232 (2006)

2006
[11]

Grabowski, M

S. Grabowski, M. Raniszewski. Sampling the suﬃx array wi th minimizers. In Porc. of String Processing and Information Retrieval (SPIRE 2015 ), Lecture Notes in Com- puter Science, vol 9309, Springer, pp. 287–298 (2015)

2015
[12]

R. N. Horspool, Practical fast searching in strings, Sof tware: Practice & Experience 10 (6), pp. 501–506 (1980)

1980
[13]

Karkkainen, E

J. Karkkainen, E. Ukkonen, Sparse suﬃx trees, in: Proc. 2 nd Annual International Conference on Computing and Combinatorics (COCOON), LNCS 1 090, pp. 219–230 (1996)

1996
[14]

Klein, D

S.T. Klein, D. Shapira. A new compression method for comp ressed matching. In: Data Compression Conference, IEEE. pp. 400–409 (2000)

2000
[15]

D. E. Knuth, J. H. Morris, V. R. Pratt, Fast pattern matchi ng in strings, SIAM J. Comput. 6 (2), pp. 323–350 (1977)

1977
[16]

A text compression scheme that allows fast searc hing directly in the com- pressed ﬁle

Manber. A text compression scheme that allows fast searc hing directly in the com- pressed ﬁle. ACM Trans. Inform. Syst., 15(2), pp.124–136 (1 997)
[17]

Manber, G

U. Manber, G. Myers, Suﬃx arrays: A new method for online s tring searches, SIAM J. Comput. 22 (5), pp. 935–948 (1993)

1993
[18]

Moura, G

E. Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates. Fas t and ﬂexible word searching on compressed text. ACM Transactions on Informat ion Systems (TOIS), 18(2), pp.113–139 (2000)

2000
[19]

Navarro, J

G. Navarro, J. Tarhio. LZgrep: A Boyer-Moore string matc hing tool for Ziv-Lempel compressed text. Software Practice & Experience, vol. 35, p p. 1107–1130 (2005)

2005
[20]

Shibata, T

Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohar a, T. Shinohara, S. Arikawa: Speeding Up Pattern Matching by Text Compression. CIAC 2000: pp. 306– 315

2000
[21]

A. C. Yao, The complexity of pattern matching for a random string, SIAM J. Comput. 8 (3), pp. 368–387 (1979)

1979

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Apostolico, The myriad virtues of suﬃx trees, in: A

A. Apostolico, The myriad virtues of suﬃx trees, in: A. Apo stolico, Z. Galil (Eds.), Combinatorial Algorithms on Words, Vol. 12 of NATO Advanced Science Institutes, Series F, Springer-Verlag, pp. 85–96 (1985)

work page 1985

[2] [2]

Boyer, J.S

R.S. Boyer, J.S. Moore. A fast string searching algorithm . Commun. ACM 20(10), 762-772 (1977)

work page 1977

[3] [3]

Cantone, S

D. Cantone, S. Faro, E. Giaquinta: Adapting Boyer-Moore- like Algorithms for Searching Huﬀman Encoded Texts. Int. J. Found. Comput. Sci. 23(2), pp. 343–356 (2012)

work page 2012

[4] [4]

Cantone, S

D. Cantone, S. Faro, A. Pavone: Speeding Up String Matchin g by Weak Factor Recognition. Stringology 2017, pp. 42–50 (2017)

work page 2017

[5] [5]

Claude, G

F. Claude, G. Navarro, H. Peltola, L. Salmela, J. Tarhio, S tring matching with alphabet sampling, Journal of Discrete Algorithms, vol. 11 , pp. 37–50 (2012)

work page 2012

[6] [6]

Crochemore, A

M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. L ecroq, W. Plandowski, W. Rytter, Speeding up two string-matching algorithms, Alg orithmica 12 (4), pp. 247–267 (1994)

work page 1994

[7] [7]

45 (2 ), pp

S Faro, T Lecroq, The Exact Online String Matching Problem : a Review of the Most Recent Results, ACM Computing Surveys (CSUR) vol. 45 (2 ), pp. 13 (2013)

work page 2013

[8] [8]

S. Faro, T. Lecroq, S. Borz ` ı, S. Di Mauro, and A. Maggio. Th e String Matching Algorithms Research Tool. In Proc. of Stringology , pages 99–111, 2016

work page 2016