Questions tagged [string-matching]

The tag has no usage guidance.

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8
votes
0answers
194 views

Simplifying the disjoint union of wildcard strings

Setting: patterns with "don't care" symbols, binary alphabet. For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$. We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) ...
4
votes
0answers
84 views

Fixed-parameter tractability of string homomorphism

String homomorphism is a function $h: \Sigma \to \Sigma^*$, which naturally defines a homomorphism on strings from $\Sigma^*$ with respect to concatenation. We denote $H(s) = h(s_1)h(s_2)\dots h(s_n)$ ...
1
vote
0answers
142 views

The edit distance of BWT of two strings with one difference

Let $BWT$ stand for the Burrows-Wheeler transform on strings. What is the maximal edit distance of $BWT(w)$ and $BWT(u)$, if $w$ and $u$ differ only in one character.
0
votes
0answers
284 views

Algorithm to merge two incomplete sequences of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
0
votes
0answers
501 views

suffix tree: about Ukkonen's algorithm

I have specific question about suffix trees. I am reading the book Algorithms on strings_trees and sequence. I cannot understand details of Ukkonen's algorithm for constructing suffix trees. Why ...
0
votes
1answer
485 views

Is the running time of Boyer-Moore linear?

With pattern length $M$, text length $N$, and alphabet $\Sigma$, is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$ (even when $M$ grows larger than $|\Sigma|$)? Are there any sublinear ...