Questions tagged [string-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
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 ...
24
votes
8answers
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, ...
1
vote
1answer
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 ...
5
votes
2answers
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 ...
10
votes
2answers
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 ...
9
votes
1answer
329 views

Pattern matching with don't cares: multiple patterns

Kalai's 2-page SODA paper gives a simple and efficient algorithm for pattern matching with don't cares (wildcards that match one character). In essence, it is as easy as convolution. But what happens ...
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.
12
votes
1answer
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 ...
2
votes
1answer
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 ...
11
votes
1answer
982 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 ...
0
votes
1answer
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 ...
4
votes
1answer
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)...
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 ...
3
votes
2answers
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 ...
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): ...
1
vote
1answer
482 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." ...
2
votes
3answers
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 ...
26
votes
1answer
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 ...
0
votes
1answer
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 ...
10
votes
3answers
734 views

Permutation pattern matching in strings

Loosely speaking, permutation pattern matching deals with problems of the following kind: Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a subsequence $...
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) ...
13
votes
2answers
875 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 ...
10
votes
4answers
5k views

Can Suffix trees be used to find all common substrings?

I am trying to use suffix trees to compare string sequences. I have found implementations/theory for the longest common sub string problem using suffix trees. However, What i am looking for is a ...
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 ...
6
votes
1answer
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 ...
2
votes
2answers
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. ...
20
votes
2answers
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 ...
0
votes
1answer
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.
-4
votes
3answers
125 views

Text Analyze and Processing

What algorithms do you know regarding text analyze/processing? Detailed, I need to "find out" the most used words, sentences, words' combinations, their category etc (these are just examples, moreover ...
9
votes
1answer
561 views

Deciding if a wildcard string is completely matched by another wildcard string in a set

Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the ...
3
votes
1answer
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 ...
-1
votes
1answer
384 views

Locate “N Gram” substrings that are smallest distance away from a target string N character long

I am looking for an algorithm, or code, preferably in Python that would help me locate substrings, N characters long, of exisiting strings that are closest to a target string N character long. ...
8
votes
4answers
735 views

Intermediate/Coding representation for Levenshtein Distance

The phrases: The quick brown fox jumps over the lazy dog [A] and The uick brown fox jumps oower the lazy dog [B] can be compared using Levenshtein Distance algorithm to determine similarity ...