Questions tagged [string-matching]
Use for generic string matching that may be exact substring matching (though then prefer the tag `exact-string-matching`), may be matching to a regular expression, or may be approximate matching (e.g. finding substrings within a given Levenshtein distance of a reference string)
77 questions
1
vote
0
answers
35
views
Sparse bit string pattern matching
Suppose there are two strings of bits. Let's call them the needle (n) and the haystack (h).
We'll say that the needle matches ...
- 111
1
vote
1
answer
46
views
Knuth–Morris–Pratt algorithm - Determine the next position of the proper prefix of the pattern string
When I learn Knuth–Morris–Pratt algorithm, I got a function f from the book Fundamentals of Data Structures in C.
...
- 11
1
vote
1
answer
95
views
A problem maybe related to pattern-matching
Let $\Sigma_{1}=\{a,b\}$ and $\Sigma_{2}=\{t,f\}$.
Define the function $f_{w}:\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ for every $w\in\Sigma_{1}^{*}$; $f_{w}(w')\in\Sigma_{2}^{*}$ is the word obtained ...
- 11
0
votes
0
answers
21
views
What sub-sequences do strings for the standard scientific units have in common?
As motivation, a Space Craft known as the Mars Climate Orbiter failed in the year 1999.
The failure occurred because the distinction between pound-force seconds and newton-seconds was made as an ...
0
votes
0
answers
29
views
Use case for string matching in a 2 by n grid
In a 2 by n grid there is a character in each cell. A path can start at any cell and then you can move to right or down. This way each path will denote a string written by characters on cells visited ...
1
vote
0
answers
45
views
Simultaneous matching of all Caesar rotations of a pattern in a text
Suppose we have an alphabet of size $S$, a pattern of length $P$ and a text of length $T$. We want to design an algorithm for matching all caesar rotations of the pattern $P$ in the text $T$. The ...
- 451
1
vote
1
answer
86
views
Finding the subset of a dictionary that has the minimum edit distance to a given string
I'm looking for the most efficient way of solving an Levenshtein edit distance problem.
We are given as input:
A set of strings S of size ...
- 411
0
votes
0
answers
15
views
What algrorithm computes a mutally exclusive partitioning from two regulair expressions?
The Question
A regular expression, such as AL+[EYI]+, represents a set of strings.
...
0
votes
1
answer
98
views
Shortest string which all input strings is its substring
Given a set of input strings, how do I find a shortest string S so that all input strings appear as a substring of S?
for example:
...
- 193
0
votes
1
answer
243
views
Longest prefix of string S that is also a sub-prefix of S in linear time
As the question suggest. I want an algorithm that runs in linear time which finds the longest prefix of a substring that is a sub-prefix of the same string.
Formally:
Given a string $S$ of length $n$,...
- 3
2
votes
1
answer
351
views
Understanding Rabin-Karp's rolling hash computation
Possibly related to this. Let $T$ be the text and $n$ be the length of the pattern. I understand that if substrings of $T$ are interpreted as base-$d$ numbers where $d$ is the alphabet's size, then ...
- 195
2
votes
1
answer
75
views
Complexity of right-to-left Knuth-Morris-Pratt algorithm
Suppose we modify the Knuth-Morris-Pratt string-matching algorithm to scan the pattern right-to-left a la Boyer-Moore, and consequently apply the shift rule on the right side of the cursor instead of ...
- 195
1
vote
1
answer
50
views
Compressed string lookup by name or ordinal
I have a large list of strings with associated values. I need to do a fast lookup into the list by the string prefix, but also by the string's ordinal within the list. For example,
...
- 129
0
votes
0
answers
61
views
What algorithm will determine if two strings match eachother or not?
$\require{enclose}$
Definition of parent
For any three strings $x$, $y$, and $p$, we say that $p$ is a parent of $x$ and $y$ if and only if all of the following:
$p$ is a $\enclose{updiagonalstrike, ...
0
votes
0
answers
33
views
Is it possible to find Longest common subsequence of all pair of splits of a string in better than $O(n^3)$?
I have a string $a_0a_1..a_{n-1}$
Lets say we split the string at pos $i$, so the string are
$a_0a_1....a_{i}$ and $a_{i+1}a_{i+2}....a_{n-1}$
Now I need to compute:
$max(LCS(a_0a_1....a_{i} , a_{i+1}...
- 111
2
votes
3
answers
551
views
Complexity of string comparison vs whitespace-trimmed string comparison
I recently worked on an algorithm which, among other things, checks strings for equality using the classic builtin equality operator:
str1 == str2
(I think it ...
- 73
1
vote
1
answer
64
views
How to match a string with any linear transformation of the pattern?
The following exercise in my homework is about string matching using the $KMP$ algorithm with a pattern that can be modified by a linear transformation.
Question: We're given a text $T \in \mathbb{N}^*...
- 469
1
vote
0
answers
79
views
Can suffix tree be used to match subsequences?
Given a set of strings, and a pattern - we want to compute the subset of those strings that have that pattern as a subsequence (not substring).
Everything I've read of suffix trees refer to computing ...
1
vote
0
answers
35
views
Longest substring creating palindromic substring in other string
Given two strings $s, t$, I would liketo find a maximal subsequence of $t$ (denoted as $t'$), such that the concatenation of $t'$ with its reverse ($t'_R$), is a palindromic substring of $s$.
I ...
- 111
1
vote
1
answer
361
views
Counting substrings of a string that do not contain a given string
Let's say we have a string $s[0..n-1]$ and a pattern $p[0..m-1]$ with $m < n$. I am looking for an $O(nm)$ solution to the following problem: find the number of substrings of $s$ not containing $p$ ...
- 41
4
votes
1
answer
594
views
please help me understand the algorithm for building the KMP failure function
I am struggling to grasp the algorithm for building the KMP failure function. The bulk of what is making my understanding incomplete concerns the line ...
- 39
1
vote
0
answers
33
views
Has anyone seen the following string classifier discussed?
The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea.
Given a set of ...
- 111
0
votes
0
answers
65
views
All strings in a range with a given prefix and suffix
Given a decimal number N (which has at most, 10^6 digits, actually we should look at it as a string!) and another decimal number M (which has K digits, 1 <= K <= 10^6 ), we are asked to find all ...
- 29
0
votes
1
answer
52
views
Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)
If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because ...
- 25
1
vote
0
answers
105
views
Longest palindrome after swapping operation
I know that Manacher's algorithm can be used to find the longest palindromic substring of a string in linear time.
But I want to find the longest palindromic substring after swapping any two indices ...
- 11
1
vote
1
answer
200
views
What are string matching algorithms used in text editors like Atom and sublime
I know there are many algorithms for finding a pattern in a text like Boyer Moore, KMP, RabinKarp and so on.
I want to know what is the one that is mostly prefered by text editors and IDEs, as I find ...
- 111
3
votes
1
answer
1k
views
calculating the string similarity of an optimal alignment
description of the algorithms behavior
I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
- 81
1
vote
1
answer
149
views
Subintervals during backward search of a BWT
A Burrows-Wheeler Transform (BWT) can be used to find the suffix array intervals for a pattern $P$ by issuing $p=|P|$ paired $rank$ queries
\begin{align}
s^\prime &= C[P[i]] + rank(s-1, P[i]) + 1 \...
- 133
0
votes
1
answer
36
views
Matching with specific cardinality
In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific ...
- 131
0
votes
2
answers
300
views
Find the maximum number of contiguous occurrences of smaller string s in a larger string l
Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l.
Ex.
...
- 159
1
vote
1
answer
2k
views
Can't wrap my head around on building a suffix table for Boyer Moore
My resources were the following video, as well as this video.
Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following:
k
suffix
d2
1
...
- 113
1
vote
1
answer
65
views
Is string spliting formally defined when the string delimiter is an empty string?
Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you:
...
- 113
2
votes
1
answer
335
views
Find optimal local alignment of two strings with restrictions
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
We want to find an optimal local ...
- 165
2
votes
1
answer
146
views
What is the SetHorspool string searching algorithm and how is it implemented?
What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice?
This has been implemented in 2 libraries I have come across:
https://app-...
1
vote
0
answers
553
views
Boyer-Moore jump table
I have a pattern $P$ of length $m$, i.e. $P = p_0, p_1, \ldots, p_{m-1}$
which I want to build a simple jump table for (not considering special optimizing cases for now).
I only want to build a jump ...
- 145
2
votes
1
answer
157
views
Why is KMP preprocessing O(N)?
My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from ...
- 23
3
votes
0
answers
198
views
Intellij string search and highlight algorithm
I'm searching for an alogrithm that takes two strings, a query and a string that is to be searched for the query. The algorithm should result in a 'found' when the string contains the characters of ...
2
votes
0
answers
89
views
Smart String search algorithm
I'm looking for a solution to search for strings in a large text file. I would like to match strings with as many of those words in close proximity as possible.
For example, if a query is for the ...
- 21
1
vote
2
answers
69
views
Title matching against human input
I am attempting to match human input of titles to a list of titles, and also show likely candidates when a human enters a title not known. Ideally I'd also have some way to suggest the human input of ...
- 111
2
votes
0
answers
119
views
Why Burrow's Wheeler Matching (FM-Index) is favored for DNA read matching
I noticed that FM-indexing is a preferred way to match strings in large data sets, and in particular DNA sequencing wiki-article. I know that with this method, it can eliminate space dependencies ...
- 205
0
votes
2
answers
161
views
If we want to map abbreviations of full-English words (e.g. map "Jan" to "January"), how can we identify abbreviations which map to multiple words?
Short Version:
How can we construct a trie which maps abbreviations of names-of-the-month to full-month (we map the abbreviation "mar" to "march")?
The set of all abbreviations is ...
8
votes
3
answers
12k
views
What is the expected time complexity of checking equality of two arbitrary strings?
The simple (naive?) answer would be O(n) where n is the length of the shorter string. Because in the worst case you must compare every pair of characters.
So far so good. I think we can all agree that ...
- 297
0
votes
0
answers
69
views
Hashfunction for unique character distributions
The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of ...
4
votes
3
answers
379
views
Sorting array of strings (with repetitions) according to a given ordering
We get two arrays:
ordering = ["one", "two", "three"]
and
...
- 143
3
votes
1
answer
896
views
Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?
Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of ...
1
vote
2
answers
247
views
Streaming digit-to-digit conversion from decimal to hexadecimal
I am looking for a streaming algorithm for converting a decimal number to a hexadecimal number. I am assuming the input is a string represention of a decimal number (i.e., each character is a decimal ...
- 138
3
votes
1
answer
2k
views
one-to-many matching in bipartite graphs?
Consider having two sets $L$ (left) and $R$ (right).
$R$ nodes have a capacity limit.
Each edge $e$ has a cost $w(e)$.
I want to map each of the $L$ vertices to one node from $R$ (one-to-many ...
- 53
1
vote
1
answer
1k
views
Time complexity for calculating the $LPS$ array (failure function) in KMP algorithm preprocessing
I'm studying the Knuth Morris Pratt pattern searching algorithm from here. I want to know the order of computing the $lps$ array in this algorithm - that is the array of longest proper prefixes that ...
- 115
6
votes
1
answer
297
views
Find the 'best' longest common subsequence
I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and ...
- 169
1
vote
0
answers
52
views
What algorithm to compare string against multiple patterns?
My problem can be characterized as a string-search problem for a finite amount of patterns. So Aho-Corasick algorithm would be a good first choice.
However, I have certain properties that limit the ...
- 111