Titlebook: Combinatorial Pattern Matching; 12th Annual Symposiu Gad M. Landau,Amihood Amir Conference proceedings 2001 Springer-Verlag Berlin Heidelbe

收集

不可接触

胆大

Computing the Equation Automaton of a Regular Expression in ,,) Space and Time,aton, called the equation automaton of .. The number of states in this automaton is less than or equal to the number of states in the position automaton. On the other hand, it can be computed by Antimirov’s algorithm with an ..) time complexity, whereas there exist ..) implementations for the positi

共同确定为确

Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications,at our algorithm is crucial to the effective use of block-sorting compression, and we present a linear-time algorithm to sim- ulate the bottom-up traversal of a suffix tree with a suffix array combined with the longest common prefix information.

Gratuitous

Multiple Pattern Matching Algorithms on Collage System,xt without decompression. Various algorithms have been proposed depending on underlying compression methods in the last decade. Although some algorithms for multipattern searching on compressed text were also presented very recently, all of them are only for Lempel-Ziv family compressions. In this p

COWER

Finding All Common Intervals of , Permutations,lgorithm that finds in a family of . permutations of . elements all . common intervals in optimal . time and . additional space..This extends a result by Uno and Yagiura (. 26, 290-309, 2000) who present an algorithm to find all . common intervals of . = 2 permutations in optimal . time and . space.

地壳

NOMAD

Approximate Matching of Run-Length Compressed Strings,n of . letters (m0 runs) in a text of . letters (. runs) in . time, both for LCS and Levenshtein models. Then we propose improvements for a greedy algorithm for the LCS, and conjecture that the improved algorithm has . expected case complexity. Experimental results are provided to support the conjecture.

MELON

粗糙

Asim Anwar,Boon-Chong Seet,Xue Jun Li and manipulation of various graphs..Here we give the first completely elementary treatment of this problem. We characterize . and . working directly on the origi- nal signed permutation. Moreover, our presentation leads to polynomial algorithms that can be efficiently implemented using bit-wise operations.