The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [string-matching]

The tag has no usage guidance.

34 questions
Filter by
Sorted by
Tagged with
641 views

Rabin–Karp vs Karp–Rabin

The wise other editors at Wikipedia have declined my request to move the Wikipedia article on the Rabin–Karp algorithm to what I think it should be called, the Karp–Rabin algorithm, on the basis that ...
5k views

Computing the Levenshtein distance quickly

Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance. The naive approach is, ...
1k views

n-dimensional pattern matching

What are some known results for finding an exact n-dimensional subarray inside a n-dimensional array? In 1D, it is just a string matching problem, KMP does it in linear time. In 2D, this paper shown ...
876 views

Edit distance with move operations

Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the ...
359 views

Covering string by palindromes

Given a string $w=\sigma_1\sigma_2\ldots\sigma_n$, a palindrome cover is a sequence $p_1p_2\cdots p_m$ of words $p_i$ such that $p_1p_2\cdots p_m = w$ and such that each $p_i$ is a palindrome. How ...
984 views

Fibonacci words

I came across the following problem in my old Czech algorithm textbook, sadly came with no hints or solution. "We define Fibonacci words as $F_{0}=a$, $F_{1}=b$, $F_{n+2}=F_{n}F_{n+1}$, where $a$ and ...
271 views

Complexity of Homogenizing a String

Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of ...
734 views

282 views

Fast algorithm for scoring a sequence

Let us define: $U = \left\{ u_j \right\}, 1 \leq j \leq N = 2^{L}$, the set of all different binary sequences of length $L$. $V = \left\{ v_i \right\}, 1 \leq i \leq M = \binom{L}{k}2^{k}$, the set ...
337 views

How to calculate this string-dissimilarity function efficiently?

Migrated from stackoverflow. Hello, I was looking for a string metric that have the property that moving around large blocks in a string won't affect the distance so much. So "helloworld" is close ...
689 views

Can two strings be matched as disjoint subsequences of a string?

Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a (non-contiguous)...
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)$ ...
154 views

Most frequent $aXa$ substring

Let $s\in\Sigma^*$ be a string, for some alphabet $\Sigma$. We want to find the most frequent repeated substring $q$ of $s$ such that its first character equals its last one, i.e. the most frequent ...
333 views

Using compression to improve edit distance computation

I am doing a seminar on a paper titled "Unified Compression-Based Acceleration of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common ...
132 views

What is the standard name for the function which inflates a string by duplicating each of its characters?

Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters. For ...
93 views

Find shortest prefix to generate original string by overlapping

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed). For ...
295 views

Complexity of ambiguous parsing?

Consider the following problem. We are given a set of words $W \subseteq \Sigma^*$ and a set of sentences $S \subseteq W^*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^*$, to ...
296 views

Matching substrings within two strings

I'm currently thinking about the following problem: Given two strings $S,T$ over an alphabet $\Sigma$, return back a list $L$ of common substrings described by their length and positions within them. ...
252 views

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

A very simple questions. Let B be the BWT (Burrows–Wheeler transform) of a string S. My question is, due to "grouping" of consecutive characters in BWT, is it possible to somehow know the number of ...
486 views

Why does the construction step of Aho-Corasick take linear time in the number of nodes?

The original paper's analysis of this, as far as I can tell is this: "THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords. PROOF. Straightforward." ...
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.
832 views

Algorithm: Find the first k longest substrings between two similar strings

Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.
78 views

polytime transformation from a graph to a set of binary strings

$d_H$ denotes the Hamming distance between two binary strings of the same size. The problem is stated as follows. Given any undirected graph $(V, A)$, does there always exist a one-to-one ...
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): ...
59 views

Unique Identifier Creation and Invalidation

A colleague of mine recently interviewed for a software engineering job, and he was given a problem regarding unique identifier creation and testing for validation. So, the problem is: if a generated ...
501 views

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 ...
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 ...