On-line construction of suffix trees

DOI10.1007/BF01206331zbMath0831.68027OpenAlexW2059513841WikidataQ56431604 ScholiaQ56431604MaRDI QIDQ1897476

Publication date: 27 August 1995

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01206331

zbMATH Keywords

on-line algorithm suffix tree suffix automata

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Data structures (68P05)

Related Items

On-Line Analysis And Validation Of Partially Occluded Images: Implementation And Practice, On-Line Analysis And Validation Of Partially Occluded Images: Implementation And Practice, Approximating LZ77 via Small-Space Multiple-Pattern Matching, On the Structure of Consistent Partitions of Substring Set of a Word, Adaptive learning of compressible strings, Succinct Non-overlapping Indexing, LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding, Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree, Faster repetition-aware compressed suffix trees based on block trees, c-trie++: a dynamic trie tailored for fast prefix searches, Accurate and Efficient Methods to Improve Multiple Circular Sequence Alignment, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, On the relationship between histogram indexing and block-mass indexing, Large-scale detection of repetitions, Indexing a sequence for mapping reads with a single mismatch, Data structures for computing unique palindromes in static and non-static strings, Event detection in online social network: methodologies, state-of-art, and evolution, Constructing generalized suffix trees on distributed parallel platforms, An explicit algorithm for normal forms in small overlap monoids, Efficient Algorithms for SNP Haplotype Block Selection Problems, Unnamed Item, Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions, Time-Optimal Top-$k$ Document Retrieval, Sparse suffix trees, Elastic founder graphs improved and enhanced, Unnamed Item, The longest common substring problem, Dynamic construction of an antidictionary with linear complexity, Double string tandem repeats, INDEXING GAPPED-FACTORS USING A TREE, REACHABILITY ON SUFFIX TREE GRAPHS, Minimal Unique Substrings and Minimal Absent Words in a Sliding Window, Linear time algorithm for the longest common repeat problem, Algorithms for Indexing Highly Similar DNA Sequences, Full-Text Indexes for High-Throughput Sequencing, Searching and Indexing Circular Patterns, DNA-Seq Error Correction Based on Substring Indices, String-Matching and Alignment Algorithms for Finding Motifs in NGS Data, Unnamed Item, Palindrome Pattern Matching, Sparse and Truncated Suffix Trees on Variable-Length Codes, Quick Greedy Computation for Minimum Common String Partitions, THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW, COMBINATORIAL CHARACTERIZATION OF THE LANGUAGE RECOGNIZED BY FACTOR AND SUFFIX ORACLES, WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING, On-line construction of two-dimensional suffix trees, Spaces, Trees, and Colors, Forty Years of Text Indexing, Optimal encoding of non-stationary sources, Unnamed Item, Window-accumulated subsequence matching problem is linear, Simple and flexible detection of contiguous repeats using a suffix tree, Computational aspects of mining maximal frequent patterns, Indexing Circular Patterns, FINDING ALL APPROXIMATE GAPPED PALINDROMES, Creating improvisations on chord progressions using suffix trees, Unnamed Item, Online Suffix Tree Construction for Streaming Sequences, A sublinear time string prefix square detection algorithm, Finding Gapped Palindromes Online, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, Range LCP, Online algorithms for constructing linear-size suffix trie, Searching Long Repeats in Streams, Making the Error-Controlling Algorithm of Observable Operator Models Constructive, Fuzzy Genome Sequence Assembly for Single and Environmental Genomes, Generalizations of suffix arrays to multi-dimensional matrices., IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS, THE VIRTUAL SUFFIX TREE, Seed-driven Learning of Position Probability Matrices from Large Sequence Sets., Orthogonal Range Searching for Text Indexing, Constructing suffix arrays in linear time, Space efficient linear time construction of suffix arrays, Distributed suffix trees, From Suffix Trees to Suffix Vectors, Faster Compressed Suffix Trees for Repetitive Collections, Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms., Superstrings with multiplicities, Longest Lyndon Substring After Edit, Non-Overlapping Indexing - Cache Obliviously, Longest substring palindrome after edit, A metric index for approximate string matching, On representations of ternary order relations in numeric strings, A linear time lower bound on McCreight and general updating algorithms for suffix trees, Online timestamped text indexing, The property suffix tree with dynamic properties, Order-preserving indexing, Construction of Aho Corasick automaton in linear time for integer alphabets, Multiple serial episodes matching, Computing suffix links for suffix trees and arrays, Faster index for property matching, Efficient discovery of unusual patterns in time series, Indexing factors with gaps, Succinct 2D dictionary matching, Linear-time text compression by longest-first substitution, DNA paired fragment assembly using graph theory, Shortest unique palindromic substring queries in semi-dynamic settings, Linear time construction of indexable elastic founder graphs, Compact directed acyclic word graphs for a sliding window, Efficient computation of substring equivalence classes with suffix arrays, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, EERTREE: an efficient data structure for processing palindromes in strings, A new filtration method and a hybrid strategy for approximate string matching, Validating the Knuth-Morris-Pratt failure function, fast and online, Palindrome pattern matching, String analysis by sliding positioning strategy, Matching a set of strings with variable length don't cares, On-line construction of position heaps, Reverse engineering of compact suffix trees and links: a novel algorithm, Linking indexing data structures to de Bruijn graphs: construction and update, Generalizations of suffix arrays to multi-dimensional matrices., Truncated suffix trees and their application to data compression., On-line suffix tree construction with reduced branching, A new efficient indexing algorithm for one-dimensional real scaled patterns, Linear-time construction of two-dimensional suffix trees, On demand string sorting over unbounded alphabets, On-line construction of parameterized suffix trees for large alphabets, The indexing for one-dimensional proportionally-scaled strings, 2-dimensional palindromes with $k$ mismatches, PSIST: a scalable approach to indexing protein structures using suffix trees, Finding patterns and periods in Cartesian tree matching, Generalized substring compression, Efficiency issues in the KBMAG procedure, Verifying and enumerating parameterized border arrays, Text indexing with errors, I/O-efficient data structures for non-overlapping indexing, Towards a real time algorithm for parameterized longest common prefix computation, Experimental evaluation of algorithms for computing quasiperiods, Fast profile matching algorithms - A survey, Property matching and weighted matching, Computing longest palindromic substring after single-character or block-wise edits, Fast algorithm for partial covers in words, Palindromic trees for a sliding window and its applications, Inferring strings from suffix trees and links on a binary alphabet, Finding maximal 2-dimensional palindromes, A new decomposition technique for maximal clique enumeration for sparse graphs, Efficient enumeration of maximal induced bicliques, Fast compressed self-indexes with deterministic linear-time construction, $xkcd$-repeats: a new taxonomy of repeats defined by their context diversity, On-line construction of compact suffix vectors and maximal repeats, Efficient on-line repetition detection, Computing regularities in strings: a survey, On-line construction of compact directed acyclic word graphs, Linear time algorithms for finding and representing all the tandem repeats in a string, A quick tour on suffix arrays and compressed suffix arrays, Ternary directed acyclic word graphs, On average sequence complexity, Optimal prefix and suffix queries on texts, Selected combinatorial problems of computational biology, Quick greedy computation for minimum common string partition, On suffix extensions in suffix trees, Improving on-line construction of two-dimensional suffix trees for square matrices, Finding the longest common nonsuperstring in linear time, Succinct non-overlapping indexing, Mining full, inner and tail periodic patterns with perfect, imperfect and asynchronous periodicity simultaneously, Suffix tree characterization of maximal motifs in biological sequences, Absent words in a sliding window with applications, Indexing weighted sequences: neat and efficient, Efficient pattern matching in elastic-degenerate strings, Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays, The exact multiple pattern matching problem solved by a reference tree approach, Two-dimensional maximal repetitions, Counter based suffix tree for DNA pattern repeats, Fully-online suffix tree and directed acyclic word graph construction for multiple texts, Real two dimensional scaled matching, Discovering subword associations in strings in time linear in the output size, Computing the longest common substring with one mismatch, Efficient indexing algorithms for one-dimensional discretely-scaled strings, The suffix binary search tree and suffix AVL tree, Data compression for proof replay, Off-line and on-line algorithms for closed string factorization, A new method for approximate indexing and dictionary lookup with one error, Sliding suffix tree, A speed-up for the commute between subword trees and DAWGs., Reducing space for index implementation., A suffix tree or not a suffix tree?, Dictionary matching with a few gaps, On maximal repeats in strings, Suffix trays and suffix trists: structures for faster text indexing, Space-efficient representation of truncated suffix trees, with applications to Markov order estimation, Computing minimal unique substrings for a sliding window

Cites Work