Skip to main content
6 votes

The Dyck Language Correction Problem

The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time B. Saha, ...
Yossi Gil's user avatar
  • 531
6 votes
Accepted

Complexity of Homogenizing a String

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 ...
isaacg's user avatar
  • 806
5 votes
Accepted

Pattern matching with don't cares: multiple patterns

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 $...
Janne H. Korhonen's user avatar
5 votes

Do Knuth-Morris-Pratt and Booth’s LCS algorithm work in linear time on lists of lists of integers?

This doesn't answer your question about why your naive comparisons are fast, but the following appears to allow comparisons in constant time: Concatenate the lists of integers together Compute the ...
David Eppstein's user avatar
3 votes

Computing the Levenshtein distance quickly

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,...
Gaslight Deceive Subvert's user avatar
3 votes

The Dyck Language Correction Problem

If by "edit operations" you mean single character insertions, deletions, and substitutions then I believe a greedy algorithm works. Let $x_i$ be the number of ] minus the number of [ in the ...
Whosyourjay's user avatar
2 votes

Complexity of Homogenizing a String

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 ...
Peter Leupold's user avatar
2 votes
Accepted

Are string palindrome questions practically interesting?

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 ...
Bjørn Kjos-Hanssen's user avatar
2 votes
Accepted

Proof techniques for string algorithms?

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 ...
Christian Komusiewicz's user avatar
2 votes

Find shortest prefix to generate original string by overlapping

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 ...
Jeffrey Shallit's user avatar
1 vote

How well can shortest common supersequence over small alphabet size be approximated?

Does this remain true if $n$ is bounded? No. When $n=O(1)$, there is a constant-factor approximation algorithm. See Lemma 1 below. Does this remain true if $n$ is sublinear in $|L|$? Yes. For ...
Neal Young's user avatar
  • 10.8k
1 vote

Match a string agains a set of regexes

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 ...
Mohemnist's user avatar
  • 230
1 vote

BWT: is it possible to predict the next character in a sequence?

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 ...
KWillets's user avatar
  • 181
1 vote

How to calculate this string-dissimilarity function efficiently?

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.
ybungalobill's user avatar

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