×

Found 605 Documents (Results 1–100)

Dynamic suffix array with polylogarithmic queries and updates. (English) Zbl 07774446

Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1657-1670 (2022).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Elastic-degenerate string matching with 1 error. (English) Zbl 07719335

Castañeda, Armando (ed.) et al., Latin 2022: theoretical informatics. 15th Latin American symposium, Guanajuato, Mexico, November 7–11, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13568, 20-37 (2022).
MSC:  68Qxx 68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv HAL

Pattern masking for dictionary matching. (English) Zbl 07788638

Ahn, Hee-Kap (ed.) et al., 32nd international symposium on algorithms and computation, ISAAC 2021, Fukuoka, Japan, December 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 212, Article 65, 19 p. (2021).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Document retrieval hacks. (English) Zbl 07700594

Coudert, David (ed.) et al., 19th international symposium on experimental algorithms, SEA 2021, Nice, France, June 7–9, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 190, Article 12, 12 p. (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

An invertible transform for efficient string matching in labeled digraphs. (English) Zbl 07696006

Gawrychowski, Paweł (ed.) et al., 32nd annual symposium on combinatorial pattern matching, CPM 2021, Wrocław, Poland, July 5–7, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 191, Article 20, 14 p. (2021).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI arXiv

A compact index for Cartesian tree matching. (English) Zbl 07696004

Gawrychowski, Paweł (ed.) et al., 32nd annual symposium on combinatorial pattern matching, CPM 2021, Wrocław, Poland, July 5–7, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 191, Article 18, 19 p. (2021).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI

On-line pattern matching on \(D\)-texts (invited talk). (English) Zbl 07695989

Gawrychowski, Paweł (ed.) et al., 32nd annual symposium on combinatorial pattern matching, CPM 2021, Wrocław, Poland, July 5–7, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 191, Article 3, 2 p. (2021).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI

Efficient string matching based on a two-step simulation of the suffix automaton. (English) Zbl 07495113

Maneth, Sebastian (ed.), Implementation and application of automata. 25th international conference, CIAA 2021, virtual event, July 19–22, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12803, 165-177 (2021).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

Indexing isodirectional pointer sequences. (English) Zbl 07765393

Cao, Yixin (ed.) et al., 31st international symposium on algorithms and computation, ISAAC 2020, Hong Kong, China, virtual conference, December 14–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 181, Article 35, 15 p. (2020).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Linear time construction of indexable founder block graphs. (English) Zbl 1515.92048

Kingsford, Carl (ed.) et al., 20th international workshop on algorithms in bioinformatics. WABI 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 172, Article 7, 18 p. (2020).
MSC:  92D20 92D10 92-08
PDFBibTeX XMLCite
Full Text: DOI arXiv

On indeterminate strings matching. (English) Zbl 07651105

Gørtz, Inge Li (ed.) et al., 31st annual symposium on combinatorial pattern matching, CPM 2020, Copenhagen, Denmark, June 17–19, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 161, Article 14, 14 p. (2020).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI

Detecting \(k\)-(Sub-)cadences and equidistant subsequence occurrences. (English) Zbl 07651103

Gørtz, Inge Li (ed.) et al., 31st annual symposium on combinatorial pattern matching, CPM 2020, Copenhagen, Denmark, June 17–19, 2020. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 161, Article 12, 11 p. (2020).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fast and linear-time string matching algorithms based on the distances of \(q\)-gram occurrences. (English) Zbl 1515.68386

Faro, Simone (ed.) et al., 18th international symposium on experimental algorithms, SEA 2020, Catania, Italy, June 16–18, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 160, Article 13, 13 p. (2020).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI arXiv

The complexity of the approximate multiple pattern matching problem for random strings. (English) Zbl 07651042

Drmota, Michael (ed.) et al., 31st international conference on probabilistic, combinatorial and asymptotic methods for the analysis of algorithms, AofA 2020, Klagenfurt, Austria (virtual conference), June 15–19, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 159, Article 3, 15 p. (2020).
MSC:  68W40
PDFBibTeX XMLCite
Full Text: DOI

String indexing with compressed patterns. (English) Zbl 07650895

Paul, Christophe (ed.) et al., 37th international symposium on theoretical aspects of computer science, STACS 2020, Montpellier, France, March 10–13, 2020. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 154, Article 10, 13 p. (2020).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Complexity issues of string to graph approximate matching. (English) Zbl 1437.68208

Leporati, Alberto (ed.) et al., Language and automata theory and applications. 14th international conference, LATA 2020, Milan, Italy, March 4–6, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12038, 248-259 (2020).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parallel duel-and-sweep algorithm for the order-preserving pattern matching. (English) Zbl 1440.68342

Chatzigeorgiou, Alexander (ed.) et al., SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12011, 211-222 (2020).
MSC:  68W32 68W10
PDFBibTeX XMLCite
Full Text: DOI

Internal dictionary matching. (English) Zbl 07650255

Lu, Pinyan (ed.) et al., 30th international symposium on algorithms and computation, ISAAC 2019, Shanghai University of Finance and Economics, Shanghai, China, December 8–11, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 149, Article 22, 17 p. (2019).
MSC:  68W32 68P05 68W40
PDFBibTeX XMLCite
Full Text: DOI

String matching: communication, circuits, and learning. (English) Zbl 07650123

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 56, 20 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI arXiv

RLE edit distance in near optimal time. (English) Zbl 07561710

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 66, 13 p. (2019).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the complexity of string matching for graphs. (English) Zbl 07561548

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 55, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Even faster elastic-degenerate string matching via fast matrix multiplication. (English) Zbl 07561514

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 21, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Applications of \(V\)-order: suffix arrays, the Burrows-Wheeler transform & the FM-index. (English) Zbl 1522.68767

Das, Gautam K. (ed.) et al., WALCOM: algorithms and computation. 13th international conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11355, 329-338 (2019).
PDFBibTeX XMLCite
Full Text: DOI

On the decision tree complexity of string matching. (English) Zbl 1524.68153

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 45, 13 p. (2018).
MSC:  68Q25 68W32
PDFBibTeX XMLCite
Full Text: DOI arXiv

Order-preserving pattern matching indeterminate strings. (English) Zbl 1497.68602

Navarro, Gonzalo (ed.) et al., 29th annual symposium on combinatorial pattern matching, CPM 2018, July 2–4, 2018, Qingdao, China. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 105, Article 2, 15 p. (2018).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI arXiv

Dictionary matching in elastic-degenerate texts with applications in searching VCF files on-line. (English) Zbl 1493.68410

D’Angelo, Gianlorenzo (ed.), 17th symposium on experimental algorithms, SEA 2018, June 27–29, 2018, L’Aquila, Italy. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 103, Article 16, 14 p. (2018).
MSC:  68W32 68W27
PDFBibTeX XMLCite
Full Text: DOI

Parallel string matching. (English) Zbl 1483.68507

Desprez, Frédéric (ed.) et al., Euro-Par 2016: parallel processing workshops. Euro-Par 2016 international workshops, Grenoble, France, August 24–26, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10104, 187-198 (2017).
MSC:  68W32 68W10
PDFBibTeX XMLCite
Full Text: DOI Link

Streaming periodicity with mismatches. (English) Zbl 1467.68237

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 42, 21 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fast and simple jumbled indexing for binary run-length encoded strings. (English) Zbl 1434.68730

Kärkkäinen, Juha (ed.) et al., 28th annual symposium on combinatorial pattern matching. CPM 2017, Warsaw, Poland, July 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 78, Article 19, 9 p. (2017).
MSC:  68W32 68W40
PDFBibTeX XMLCite
Full Text: DOI arXiv

On-line pattern matching on similar texts. (English) Zbl 1434.68734

Kärkkäinen, Juha (ed.) et al., 28th annual symposium on combinatorial pattern matching. CPM 2017, Warsaw, Poland, July 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 78, Article 9, 14 p. (2017).
MSC:  68W32 68W27
PDFBibTeX XMLCite
Full Text: DOI

Position heaps for parameterized strings. (English) Zbl 1434.68125

Kärkkäinen, Juha (ed.) et al., 28th annual symposium on combinatorial pattern matching. CPM 2017, Warsaw, Poland, July 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 78, Article 8, 13 p. (2017).
MSC:  68P05 68W27 68W32
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the benefit of merging suffix array intervals for parallel pattern matching. (English) Zbl 1380.68471

Grossi, Roberto (ed.) et al., 27th annual symposium on combinatorial pattern matching, CPM 2016, Tel Aviv, Israel, June 27–29, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-012-5). LIPIcs – Leibniz International Proceedings in Informatics 54, Article 26, 11 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A practical semi-external memory method for approximate pattern matching. (English) Zbl 1364.68382

Vizzotto, Juliana K. (ed.), Proceedings of the 3rd workshop-school on theoretical computer science, Porto Alegre, Brazil, October 14–16, 2015. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 324, 107-122 (2016).
MSC:  68W32 68W40
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Serial

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software