Titlebook: Combinatorial Pattern Matching; 25th Annual Symposiu Alexander S. Kulikov,Sergei O. Kuznetsov,Pavel Pev Conference proceedings 2014 Springe

Chivalrous

支架

Compactness-Preserving Mapping on Trees,ance at most . to . in a graph .. We call this problem . (CPM). In the paper we study CPM with input graphs being trees and present a dichotomy of classical complexity with respect to different values of . and .. CPM on trees can be solved in polynomial time only if . ≤ 2 and . ≤ 1.

痛得哭了

‘Safety and Cybersecurity in a Digital Age’n of any substring of the text in . time, where . is the number of distinct factors in the decomposition. For the maximal suffix problem we give a linear-space structure with . query time and . preprocessing time, i.e., we manage to achieve both the optimal query and the optimal construction time simultaneously.

Admonish

https://doi.org/10.1007/978-3-030-28191-5 that allows us to efficiently find the next occurrence of a given character after a given position in a compressed string. This data structure in turn is based on a new data structure for the tree color problem, where the node colors are packed in bit strings.

constitute

Velislava Simeonova,Kalina Milkovaof blocks they contain (a block being maximal substring such that all letters in the substring are equal), and the alphabet size Σ. For instance, we show that . and . are NP-hard even if the input strings have only . letter.

有组织

Indelible

通便

https://doi.org/10.1007/978-3-662-62153-0lications in bioinformatics. In this paper we develop the first randomized parameterized algorithms for CSP. Not only are the randomized algorithms much simpler than their deterministic counterparts, their expected-time complexities are also significantly better than the previously best known (deterministic) algorithms.

演讲

https://doi.org/10.1007/978-3-662-62153-0me is .((loglog.) log.), where . is the size of the alphabet..A byproduct of this paper is an Aho-Corasick automaton that can be constructed with only a compact working space, which is the first of its type to the best of our knowledge.

Pessary

On the Efficiency of the Hamming C-Centerstring Problems,a generalization is necessary for clustering. One needs to consider a partition into a number of sets, each with a distinct centerstring. In this paper we define two natural versions of the consensus problem for c centerstrings. We analyse the hardness and fixed parameter tractability of these probl