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)
74
questions
1
vote
0
answers
40
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 ...
- 431
0
votes
0
answers
14
views
KMP search: Can a shift by partial match prefix by non-suffix match lead to exact match?
Consider the following step where 'abaab', upon failed mismatch, 'ab' the prefix is followed by aligning at 'ab' the suffix. What confuses me is the reason for being able to discard the possibility of ...
- 101
1
vote
1
answer
45
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
14
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
47
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
0
answers
39
views
Performing fuzzy search queries on a large database of strings
I have a large database of strings (~10 million)
I need to perform fuzzy search queries which would find the best match inside that database.
The best match meaning the one that has the highest 'score'...
- 113
0
votes
1
answer
177
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
300
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 ...
- 183
2
votes
1
answer
67
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 ...
- 183
1
vote
1
answer
29
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
59
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
31
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
311
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
63
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}^*...
- 453
1
vote
0
answers
52
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
243
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
377
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
56
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
41
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
59
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
154
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
709
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
106
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
32
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
226
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
1k
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
63
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
321
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
109
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
433
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
132
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 ...
- 21
3
votes
0
answers
184
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
76
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
61
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
97
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
135
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
10k
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
49
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
346
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
622
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
229
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 ...
- 38
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
996
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
5
votes
1
answer
212
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 ...
- 159
1
vote
0
answers
36
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
1
vote
0
answers
78
views
How does the asterisk (*) work in the wildcard matching problem?
This is a wildcard matching problem. Given a pattern P containing letters and character * that can match an arbitrary string of characters (including an empty string), my task is to write a polynomial-...
- 21
7
votes
1
answer
762
views
How to perform orthogonal check on two circular binary strings?
Say we have two circular binary strings $a = a_0a_1...a_{n-1}$ and $b = b_0b_1...b_{n-1}$ with arbitary starting point, and define a and b are orthogonal if $\sum_{i=0}^{n-1}a_ib_i = 0$.
Is there a $...
- 71
2
votes
1
answer
300
views
reverse string to pattern matching
I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.:
Patterns:
...
- 123