# Tag Info

## Hot answers tagged string-matching

25

I've asked Dick personally out of curiosity a few years back. He said that as far as he knows Rabin-Karp was a random switch many years after the paper was first published. He also indicated that it is his understanding that Michael would say the same thing if asked, since at some point they had talked about it.

12

The obvious way to go is dynamic programming: let $F(i,j)$ store the two letters for which a Fibonacci word of order $i$ starts at position $j$, and calculate this by looking at $F(i-2,j)$ and $F(i-1,j+\operatorname{fib}(i))$. This takes $O(n \log n)$ time at most, because there are only logarithmically many possible values of $i$. But I suspect that there ...

9

This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example: A subquadratic algorithm for minimum palindrome factorization by Fici et al EERTREE: An Efficient Data Structure for Processing Palindromes in Strings by Rubinchik and Shur.

6

This problem is NP-complete, by reduction from Minimum Hitting Set. In minimum hitting set, we are given a universe, $U$, and a set of sets $S$ such that $\forall s \in S, s \subset U$. The objective is to find $H \subset U$ of smallest size such that $\forall s \in S, \exists h \in H$ such that $h \in s$. The reduction is as follows: The string is as ...

5

For the multiple pattern case, it seems that simply scanning for each of the might be the best possible solution, at least unless the strong exponential-time hypothesis fails. Recall that given sets $S_1, S_2, \dotsc, S_n$ and $T_1, T_2, \dotsc, T_n$ over universe $[m]$, if we could decide if there are $S_i$ and $T_j$ such that $S_i \cup T_j = [m]$ in time $... 5 The problem becomes easier, if we consider long deletions and substring copying instead of transpositions. Assume that we are using the standard dynamic programming algorithm for edit distance computation, and that an expensive operation of length$k$increases the distance by$ak+b$, for some constants$a,b \ge 0$. These constants may be different for long ... 5 As commented by Serge Gaspers, for$k=0$the problem is Sorting by Transpositions, and was introduced by Bafna and Pevzner in 1995. Its NP-hardness has been proved only in 2010; see Laurent Bulteau, Guillaume Fertin, and Irena Rusu, "Sorting by Transpositions is Difficult". 4 Case k=2 Perhaps you can use the following polynomial time dynamic approach: Keep a table$T_i$of$(|S_1|+1)(|S_2|+1)$pairs, in which element$(x,y)=1$if and only if after scanning$i$elements of the reference string$S$,$x$characters of$S_1$have been found, and$y$characters of$S_2$have been found (without overlaps). Every pair of the table$...

3

As pointed out by Marcus Ritt, the correct name for this operation seems to be stutter. As far as I could determine, it has mostly been used in the field of concurrency theory, where I could trace it back at least to Lamport's 1983 seminal paper on temporal logic.

3

I think what you want is the Wagner-Fischer algorithm: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm The key insight is that, since the dictionary you are traversing through is sorted, two consecutive words are very likely to share a long prefix so you don't need to update the whole matrix for each distance calculation.

2

Here is the first part of the answer (without swapping). I restated some of the definitions to make them clearer (I think), as I was somewhat confused by the statement of the question. Introduction to the problem and its practical importance I do not know the motivation for the question, as it was not given. However this is a known problem of natural ...

2

Yes. If the graph is regular there is a trivial scheme. Fix some ordering of the edges, and define $f(v)$ to be $0$ at the corresponding position of a particular edge if $v$ is not incident to that edge, and $1$ is $v$ is incident to the edge. If the graph is $k$-regular, then $d_H(f(v),f(u))$ is $2k-2$ if $u$ and $v$ are adjacent, and $2k$ if they are not. ...

2

I had a use for palindromes as follows: A string of length $n$ and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal. Now after identifying you may ask how many equivalence classes have certain properties. And then the number of equivalence classes is directly related to the number ...

2

There is some work on developing an algebraic or grammar-based view of string algorithms, for example Robert Giegerich, Carsten Meyer, Peter Steffen: A discipline of dynamic programming over sequence data. Sci. Comput. Program. 51(3): 215-263 (2004) Robert Giegerich, Hélène Touzet: Modeling Dynamic Programming Problems over Sequences and Trees with Inverse ...

2

You are asking about "quasiperiodicity". This is a well-studied topic and a google scholar search will turn up many papers about it. For example, there is an $O(n (\log n)^2)$ algorithm here and an $O(n \log n)$ algorithm here.

2

Look at the number of changes from one letter to the other in your string, which you could see as a measure for the string's inhomogenity. With every (useful) move of a subsequence you reduce this number by one if the subsequence you move is preceded and followed by two distinct letters. Otherwise you reduce the inhomogenity by two. So for a string with k ...

1

Hyperscan is a high-performance multiple regex matching library that uses hybrid automata techniques to allow simultaneous matching of large numbers of regular expressions across streams of data. They explained their approach here: https://www.hyperscan.io/2015/10/20/match-regular-expressions Apparently, they didn't find a fast algorithm (in the worst case) ...

1

In general, no, but it's difficult to prove a negative given that there might be some data structure equivalent to a BWT that provides the prediction capability. The L vector in the BWT is simply a list of the input string's characters sorted by their following context, i.e. the suffix that begins immediately after each character. Its information content ...

1

We get to cheat a little bit more, actually. Let $k=|\Sigma|$ If $q = aXbYbZa$ is a pattern, then $bYb$ occurs at least as many times as $q$. Thus, we only need to find patterns $cWc$ where $W$ contains no repeats and does not contain $c$. This means that the length of $q$ is at most $k+1$ We are going to build a trie-like structure where each node ...

1

Yes, you can solve the problem using standard techniques. However, the question may easily be homework, so here is just a hint: You never need to consider words of the form $aXaYa$, as they cannot be the only most frequent ones.

1

Using for reference, Aho and Corasick, Efficient string matching: an aid to bibliographic search (Communications of the ACM, 18(6):333–340, 1975) (PDF). Algorithm 2 is mostly creating a trie or "keyword tree" in the paper. Important Note: They make the assumption that $g(s, a) = \texttt{fail}$ if either $a$ is undefined, or $g(s, a)$ hasn't been ...

1

For anyone interested: I implemented The String Edit Distance Matching Problem with Moves by Graham Cormode and S. Muthukrishnan. It essentially approximates the described metric in linear time.

Only top voted, non community-wiki answers of a minimum length are eligible