Combinatorial Pattern Matching: ... Annual SymposiumSpringer-Verlag, 2005 - Combinatorial analysis |
From inside the book
Results 1-3 of 84
Page 69
... matching cannot detect the similarity between the two passages ) . One way to account for similarity between closely related but non - identical musical strings is to use what will be referred to as d - matching . In d - matching ...
... matching cannot detect the similarity between the two passages ) . One way to account for similarity between closely related but non - identical musical strings is to use what will be referred to as d - matching . In d - matching ...
Page 70
... matching on inte- ger valued data . This method is asymptotically faster than a reduction to less- than matching , when 8 is o ( āām / log m ) . For ( 8 , y ) -matching , we give a similar O ( on log m ) solution which is faster than ...
... matching on inte- ger valued data . This method is asymptotically faster than a reduction to less- than matching , when 8 is o ( āām / log m ) . For ( 8 , y ) -matching , we give a similar O ( on log m ) solution which is faster than ...
Page 87
... Matching last k + 2 characters 60 50 40 30 20 10 Matching last k + 3 characters Expected total number of comparisons 12n 11n Matching last k + 1 characters Matching last k + 2 characters Matching last k + 3 characters 10n 9n 8n 70 6n 5n ...
... Matching last k + 2 characters 60 50 40 30 20 10 Matching last k + 3 characters Expected total number of comparisons 12n 11n Matching last k + 1 characters Matching last k + 2 characters Matching last k + 3 characters 10n 9n 8n 70 6n 5n ...
Contents
Sharper Upper and Lower Bounds for an Approximation Scheme | 1 |
Text Indexing with Errors | 21 |
Succinct Suffix Arrays Based on RunLength Encoding | 45 |
Copyright | |
20 other sections not shown
Other editions - View all
Common terms and phrases
algorithm alignment alphabet Apostolico approximate automaton Bioinformatics bits bound breakpoint Burrows-Wheeler transform c-token character column complexity Computer Science consensus PQ tree consider constraints construction Corasick corresponding Crochemore data structure defined Definition denote DFTDP DIST DNA sequences dynamic programming edges edit distance efficient encoding errors example exons function gene genome given graph Hamming distance implementation input integer interval label Lemma length linear LNCS mass matching problem Max-SNP maximal median minimal consensus PQ mismatches motif multiset node O(n log obtained occurrences optimal output pā pair Parsing path pattern matching peak permutations polynomial position PQ tree prefix prefix-free preprocessing Proc Proof protein regular expression rigid subsequence Sā score Section shift distance space spin images Springer-Verlag string matching substring suffix array suffix tree term tree Theorem trie variable vector vertex WDWG words