Titlebook: Combinatorial Pattern Matching; 4th Annual Symposium Alberto Apostolico,Maxime Crochemore,Udi Manber Conference proceedings 1993 Springer-V

GEON

Boris A. Kulik,Alexander Ya. Fridmane edit distance (. differences). For a string . of length . and an integer . our algorithm reports all locally optimal approximate repeats, ., for which the Hamming distance of . and . is at most . in O(. log (n/k)) time, or all those for which the edit distance of . and . is at most ., in O(. log . log .) time.

展览

A linear time pattern matching algorithm between a string and a tree,performed using the selected vertices as ‘bases’. A suffix tree is used effectively in the algorithm. Although the size of the alphabet is assumed to be bounded by a constant in this paper, the algorithm can be applied to the case of unbounded alphabets by increasing the time complexity to .(. log .).

sleep-spindles

Covering a string,ists a string constructed by concatenations and superpositions of . of which . is a substring. A substring . of . is called a . of . if . covers .. We present an . time algorithm for finding all the seeds of a given string of length ..

迁移

迅速飞过

PANT

Tight comparison bounds for the string prefix-matching problem,g of length .. This is a natural generalization of the string matching problem where only occurrences of the whole pattern are sought. The Knuth-Morris-Pratt string matching algorithm can be easily adapted to solve the string prefix-matching problem without making additional comparisons..In this pap

Corporeal

3-D docking of protein molecules,g design and for biomolecular recognition and interaction of proteins in general. Our algorithms have been implemented and experimented on several ‘real world’ biological examples. The preliminary experimental results show an order of magnitude improvement in the actual run-time of the algorithms in

Androgen

ARBOR

圆锥体

On the worst-case behaviour of some approximation algorithms for the shortest common supersequence orst-case performance guarantee. Both algorithms behave badly in the worst case, whether the underlying alphabet is unbounded or of fixed size. For a Tournament style algorithm proposed by Timkovskii, we show that the length of the SCS found is between ./4 and (3. + 2)/8 times the length of the opti