On the public citation graph

Squares, cubes, and time-space efficient string searching

https://doi.org/10.1007/bf01190846

0 signed · 129 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/bfb0015775openalex-snapshot

Optimal parallel pattern matching in strings

inferredcites →https://doi.org/10.1016/0022-0000(83)90002-8openalex-snapshot

Time-space-optimal string matching

inferredcites →https://doi.org/10.1016/0304-3975(92)90134-2openalex-snapshot

String-matching on ordered alphabets

inferredcites →https://doi.org/10.1016/0377-2217(89)90126-4openalex-snapshot

Efficient parallel algorithms

inferredcites →https://doi.org/10.1016/0377-2217(90)90106-lopenalex-snapshot

Efficient parallel algorithms

inferredcites →https://doi.org/10.1016/b978-0-444-88071-0.50010-2openalex-snapshot

Algorithms for Finding Patterns in Strings

inferredcites →https://doi.org/10.1137/0206024openalex-snapshot

Fast Pattern Matching in Strings

inferredcites →https://doi.org/10.1137/0209032openalex-snapshot

Saving Space in Fast String-Matching

inferredcites →https://doi.org/10.1145/116825.116845openalex-snapshot

Two-way string-matching

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.2139/ssrn.4673287openalex-extracted

inferred← citeshttps://doi.org/10.1006/jcta.1997.2843openalex-snapshot

How Many Squares Can a String Contain?

inferred← citeshttps://doi.org/10.1007/11496656_22openalex-snapshot

A New Periodicity Lemma

inferred← citeshttps://doi.org/10.1007/11880561_7openalex-snapshot

On-Line Repetition Detection

inferred← citeshttps://doi.org/10.1007/3-540-44676-1_14openalex-snapshot

Finding Approximate Repetitions under Hamming Distance

inferred← citeshttps://doi.org/10.1007/3-540-45655-4_35openalex-snapshot

Repetition Complexity of Words

inferred← citeshttps://doi.org/10.1007/3-540-45995-2_21openalex-snapshot

On Maximal Suffices and Constant-Space Linear-Time Versions of KMP Algorithm

inferred← citeshttps://doi.org/10.1007/3-540-46562-6_25openalex-snapshot

Patterns in Words versus Patterns in Trees: A Brief Survey and New Results

inferred← citeshttps://doi.org/10.1007/3-540-48321-7_31openalex-snapshot

On maximal repetitions in words

inferred← citeshttps://doi.org/10.1007/3-540-60246-1_140openalex-snapshot

A periodicity theorem on words and applications

inferred← citeshttps://doi.org/10.1007/978-0-387-26677-0_6openalex-snapshot

Sequences of Integers

inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_392openalex-snapshot

Squares and Repetitions

inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_392openalex-snapshot

Squares and Repetitions

inferred← citeshttps://doi.org/10.1007/978-3-030-32686-9_15openalex-snapshot

Searching Runs in Streams

inferred← citeshttps://doi.org/10.1007/978-3-030-39881-1_7openalex-snapshot

Shortest Covers of All Cyclic Shifts of a String

inferred← citeshttps://doi.org/10.1007/978-3-030-59212-7_19openalex-snapshot

Lyndon Words, the Three Squares Lemma, and Primitive Squares

inferred← citeshttps://doi.org/10.1007/978-3-030-67731-2_29openalex-snapshot

Clusters of Repetition Roots: Single Chains

inferred← citeshttps://doi.org/10.1007/978-3-030-86692-1_15openalex-snapshot

Lower Bounds for the Number of Repetitions in 2D Strings

inferred← citeshttps://doi.org/10.1007/978-3-031-13257-5_4openalex-snapshot

Clusters of Repetition Roots Forming Prefix Chains

inferred← citeshttps://doi.org/10.1007/978-3-031-46994-7_8openalex-snapshot

Runs of Side-Sharing Tandems in Rectangular Arrays

inferred← citeshttps://doi.org/10.1007/978-3-031-72200-4_21openalex-snapshot

Computing String Covers in Sublinear Time

inferred← citeshttps://doi.org/10.1007/978-3-031-72200-4_26openalex-snapshot

Simple Linear-Time Repetition Factorization

inferred← citeshttps://doi.org/10.1007/978-3-319-07566-2_22openalex-snapshot

Searching of Gapped Repeats and Subrepetitions in a Word

inferred← citeshttps://doi.org/10.1007/978-3-319-07566-2_24openalex-snapshot

String Range Matching

inferred← citeshttps://doi.org/10.1007/978-3-319-30000-9_19openalex-snapshot

Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats

inferred← citeshttps://doi.org/10.1007/978-3-319-62389-4_9openalex-snapshot

Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes

inferred← citeshttps://doi.org/10.1007/978-3-319-62809-7openalex-snapshot

Developments in Language Theory

inferred← citeshttps://doi.org/10.1007/978-3-319-67428-5_3openalex-snapshot

Distinct Squares in Circular Words

inferred← citeshttps://doi.org/10.1007/978-3-540-45138-9_33openalex-snapshot

Linear-Time Computation of Local Periods

inferred← citeshttps://doi.org/10.1007/978-3-540-74456-6_42openalex-snapshot

Analysis of Maximal Repetitions in Strings

inferred← citeshttps://doi.org/10.1007/978-3-540-85780-8_16openalex-snapshot

Bounds on Powers in Strings

inferred← citeshttps://doi.org/10.1007/978-3-642-10217-2_34openalex-snapshot

On the Maximal Number of Cubic Subwords in a String

inferred← citeshttps://doi.org/10.1007/978-3-642-13089-2_19openalex-snapshot

On the Maximal Number of Cubic Runs in a String

inferred← citeshttps://doi.org/10.1007/978-3-642-21458-5_16openalex-snapshot

Simple Real-Time Constant-Space String Matching

inferred← citeshttps://doi.org/10.1007/978-3-642-22321-1_1openalex-snapshot

Hunting Redundancies in Strings

inferred← citeshttps://doi.org/10.1007/978-3-662-46078-8_24openalex-snapshot

Pal k is Linear Recognizable Online

inferred← citeshttps://doi.org/10.1007/bf01955046openalex-snapshot

Data Structures and Algorithms for the String Statistics Problem

inferred← citeshttps://doi.org/10.1007/bfb0030787openalex-snapshot

Simple and flexible detection of contiguous repeats using a suffix tree Preliminary Version

inferred← citeshttps://doi.org/10.1007/s00224-022-10070-3openalex-snapshot

Factorizing Strings into Repetitions

inferred← citeshttps://doi.org/10.1007/s00224-025-10258-3openalex-snapshot

Computing String Covers in Sublinear Time

inferred← citeshttps://doi.org/10.1007/s00236-006-0014-zopenalex-snapshot

Periods in Extensions of Words

inferred← citeshttps://doi.org/10.1007/s10878-018-0300-zopenalex-snapshot

Efficient enumeration of non-equivalent squares in partial words with few holes

inferred← citeshttps://doi.org/10.1016/j.aam.2022.102371openalex-snapshot

On the number of k-powers in a finite word

inferred← citeshttps://doi.org/10.1016/j.dam.2013.10.021openalex-snapshot

A d -step approach to the maximum number of distinct squares and runs in strings

inferred← citeshttps://doi.org/10.1016/j.dam.2014.08.016openalex-snapshot

How many double squares can a string contain?

inferred← citeshttps://doi.org/10.1016/j.dam.2016.05.003openalex-snapshot

The New Periodicity Lemma revisited

inferred← citeshttps://doi.org/10.1016/j.ejc.2012.07.010openalex-snapshot

Computing regularities in strings: A survey

inferred← citeshttps://doi.org/10.1016/j.ejc.2012.07.012openalex-snapshot

On the maximum number of cubic subwords in a word

inferred← citeshttps://doi.org/10.1016/j.ic.2019.104434openalex-snapshot

Optimal bounds for computing α-gapped repeats

inferred← citeshttps://doi.org/10.1016/j.jcss.2007.09.003openalex-snapshot

Maximal repetitions in strings

inferred← citeshttps://doi.org/10.1016/j.jcss.2011.12.005openalex-snapshot

The maximal number of cubic runs in a word

inferred← citeshttps://doi.org/10.1016/j.jcss.2014.02.011openalex-snapshot

Prefix–suffix duplication

inferred← citeshttps://doi.org/10.1016/j.jcta.2004.09.002openalex-snapshot

Partial words and the critical factorization theorem

inferred← citeshttps://doi.org/10.1016/j.jcta.2005.01.006openalex-snapshot

A simple proof that a word of length n has at most 2 n distinct squares

inferred← citeshttps://doi.org/10.1016/j.jcta.2013.09.002openalex-snapshot

Lyndon words and Fibonacci numbers

inferred← citeshttps://doi.org/10.1016/j.jda.2011.03.009openalex-snapshot

The three squares lemma revisited

inferred← citeshttps://doi.org/10.1016/j.jda.2012.03.003openalex-snapshot

More results on overlapping squares

inferred← citeshttps://doi.org/10.1016/j.jda.2015.05.006openalex-snapshot

On a lemma of Crochemore and Rytter

inferred← citeshttps://doi.org/10.1016/j.jda.2017.10.004openalex-snapshot

Searching of gapped repeats and subrepetitions in a word

inferred← citeshttps://doi.org/10.1016/j.tcs.2004.06.024openalex-snapshot

Linear-time computation of local periods

inferred← citeshttps://doi.org/10.1016/j.tcs.2005.01.006openalex-snapshot

Space efficient search for maximal repetitions

inferred← citeshttps://doi.org/10.1016/j.tcs.2005.08.012openalex-snapshot

A multidimensional critical factorization theorem

inferred← citeshttps://doi.org/10.1016/j.tcs.2006.12.002openalex-snapshot

Intersecting periodic words

inferred← citeshttps://doi.org/10.1016/j.tcs.2007.03.025openalex-snapshot

A note on the number of squares in a word

inferred← citeshttps://doi.org/10.1016/j.tcs.2007.06.012openalex-snapshot

Partial words and the critical factorization theorem revisited

inferred← citeshttps://doi.org/10.1016/j.tcs.2008.08.038openalex-snapshot

Efficient on-line repetition detection

inferred← citeshttps://doi.org/10.1016/j.tcs.2009.08.024openalex-snapshot

Repetitions in strings: Algorithms and combinatorics

inferred← citeshttps://doi.org/10.1016/j.tcs.2010.08.031openalex-snapshot

Distinct squares in run-length encoded strings

inferred← citeshttps://doi.org/10.1016/j.tcs.2011.10.024openalex-snapshot

On primary and secondary repetitions in words

inferred← citeshttps://doi.org/10.1016/j.tcs.2012.01.012openalex-snapshot

The three-squares lemma for partial words with one hole

inferred← citeshttps://doi.org/10.1016/j.tcs.2012.11.040openalex-snapshot

Simple real-time constant-space string matching

inferred← citeshttps://doi.org/10.1016/j.tcs.2015.06.037openalex-snapshot

Three overlapping squares: The general case characterized & applications

inferred← citeshttps://doi.org/10.1016/j.tcs.2018.03.007openalex-snapshot

On the number of gapped repeats with arbitrary gap

inferred← citeshttps://doi.org/10.1016/j.tcs.2019.07.006openalex-snapshot

Two-dimensional maximal repetitions

inferred← citeshttps://doi.org/10.1016/j.tcs.2021.03.011openalex-snapshot

Shortest covers of all cyclic shifts of a string

inferred← citeshttps://doi.org/10.1016/j.tcs.2021.08.004openalex-snapshot

Square network on a word

inferred← citeshttps://doi.org/10.1016/j.tcs.2024.115005openalex-snapshot

Exact and inexact search for 2d side-sharing tandems

inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00121-9openalex-snapshot

Simple and flexible detection of contiguous repeats using a suffix tree

inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00448-6openalex-snapshot

Finding approximate repetitions under Hamming distance

inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00590-xopenalex-snapshot

On maximal suffixes and constant-space linear-time versions of KMP algorithm

inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00037-1openalex-snapshot

Periodicity and the golden ratio

inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00252-7openalex-snapshot

The exact number of squares in Fibonacci words

inferred← citeshttps://doi.org/10.1017/cbo9781316135228openalex-snapshot

Flexible Pattern Matching in Strings

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.001openalex-snapshot

Introduction

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.002openalex-snapshot

String matching

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.003openalex-snapshot

Multiple string matching

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.004openalex-snapshot

Extended string matching

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.005openalex-snapshot

Regular expression matching

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.006openalex-snapshot

Approximate matching

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.007openalex-snapshot

Conclusion

inferred← citeshttps://doi.org/10.1017/cbo9781316135228.008openalex-snapshot

Bibliography

inferred← citeshttps://doi.org/10.1051/ita/2010008openalex-snapshot

On the number of squares in partial words

inferred← citeshttps://doi.org/10.1051/ita:2008010openalex-snapshot

From Bi-ideals to Periodicity

inferred← citeshttps://doi.org/10.1098/rsta.2013.0138openalex-snapshot

Large-scale detection of repetitions

inferred← citeshttps://doi.org/10.1109/focs.2009.11openalex-snapshot

Exact and Approximate Pattern Matching in the Streaming Model

inferred← citeshttps://doi.org/10.1109/sffcs.1999.814634openalex-snapshot

Finding maximal repetitions in a word in linear time

inferred← citeshttps://doi.org/10.1109/spire.2000.878192openalex-snapshot

Finding repeats with fixed gap

inferred← citeshttps://doi.org/10.1137/050630180openalex-snapshot

A New Periodicity Lemma

inferred← citeshttps://doi.org/10.1142/s0129054104002297openalex-snapshot

WORD COMPLEXITY AND REPETITIONS IN WORDS

inferred← citeshttps://doi.org/10.1142/s0129054110007416openalex-snapshot

NUMBER OF OCCURRENCES OF POWERS IN STRINGS

inferred← citeshttps://doi.org/10.1142/s0129054110007738openalex-snapshot

A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE

inferred← citeshttps://doi.org/10.1142/s012905411240014xopenalex-snapshot

ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS

inferred← citeshttps://doi.org/10.1142/s0129054120400067openalex-snapshot

On the Prefix–Suffix Duplication Reduction

inferred← citeshttps://doi.org/10.1145/1412228.1455263openalex-snapshot

Succinct backward-DAWG-matching

inferred← citeshttps://doi.org/10.1145/3176653.3176660openalex-snapshot

Approximate Tandem Repeats Computation

inferred← citeshttps://doi.org/10.1145/3369935openalex-snapshot

Pattern Matching with Variables

inferred← citeshttps://doi.org/10.1515/dma-2019-0016openalex-snapshot

Existence of words over a binary alphabet free from squares with mismatches

inferred← citeshttps://doi.org/10.3103/s002713221601006xopenalex-snapshot

Square-free words with one possible mismatch

inferred← citeshttps://doi.org/10.3103/s0027132218030026openalex-snapshot

Existence of Words over Tree-Letter Alphabet not Containing Squares with Replacement Errors

inferred← citeshttps://doi.org/10.4086/cjtcs.2010.007openalex-snapshot

inferred← citeshttps://doi.org/10.4204/eptcs.252.10openalex-snapshot

Constructing Words with High Distinct Square Densities

inferred← citeshttps://doi.org/10.4213/dm1325openalex-snapshot

О существовании сколь угодно длинных слов, не содержащих квадратов с одной возможной ошибкой замещения

inferred← citeshttps://doi.org/10.4213/dm1473openalex-snapshot

О существовании слов над двухбуквенным алфавитом, не содержащих квадратов с ошибками замещения

inferred← citeshttps://doi.org/10.4230/lipics.cpm.2020.27openalex-snapshot

On Extensions of Maximal Repeats in Compressed Strings

inferred← citeshttps://doi.org/10.4230/lipics.stacs.2008.1344openalex-snapshot

Understanding Maximal Repetitions in Strings

inferred← citeshttps://doi.org/10.48550/arxiv.0907.2157openalex-snapshot

On the maximal number of highly periodic runs in a string

inferred← citeshttps://doi.org/10.48550/arxiv.1509.01221openalex-snapshot

Optimal searching of gapped repeats in a word

inferred← citeshttps://doi.org/10.51382/978-3-96100-191-0openalex-snapshot

Combinatorial Properties of Periodic Patterns in Compressed Strings

inferred← citeshttps://doi.org/10.71548/18072openalex-snapshot

COMBINATORIAL OPTIMIZATION APPROACHES TO DISCRETE PROBLEMS

inferred← citeshttps://doi.org/10.71548/22910openalex-snapshot

COMPUTING REPETITIONS IN STRINGS: CURRENT ALGORITHMS & THE COMBINATORICS OF FUTURE ONES.

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.