All Questions
Tagged with string-matching strings
35 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
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
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
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
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
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
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 ...
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 ...
6
votes
1
answer
298
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
Algorithm for searching string with wildcards
I'm trying to find efficient algorithm for checking if string with wildcards contains given substring.
The parts of the string are separated with a "." character.
So for example I have
...
- 11
0
votes
1
answer
51
views
Is there an algorithm to share parts of strings? [duplicate]
Let's say that we have the strings Hello, World, Hello and World. The algorithm I am ...
- 185
2
votes
2
answers
148
views
Sliding Window Dictionary String Matching
Consider the following problem. We are given a set of patterns (strings) $\Pi = \{\pi_i\}$, a text $s$, and a window length $k$. We want a list of all shifts $0 \le i \le |s|-k$ such that every ...
- 227
0
votes
0
answers
696
views
Returning all the combinations of a string using regex
Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches?
For example, if the string is ...
0
votes
0
answers
159
views
How use generalized suffix tree to match prefix string?
I know that generalized suffix tree can match substring for a given pattern.
But I have need a data structure which is able to
match prefix of many strings.
match sub string of of many strings.
For ...
- 123
2
votes
1
answer
399
views
Regular expression for capturing a "C-style" string
I have started to learn automata theory and languages. I am new to regular expressions.
As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
- 284
2
votes
1
answer
168
views
String matching
I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain . in it which ...
- 148
5
votes
1
answer
680
views
Find all substrings that fit the mask with asterisks
There is a problem.
Given string $text$ containing only letters and string $mask$ containing letters and asterisks (*), where asterisk means substitution of zero or more letters, find all substrings ...
- 155
0
votes
0
answers
57
views
Dictionary matching problem: dictionary size estimation
Suppose we solve dictionary matching problem for $d$ patterns with the Aho-Corasick algorithm. Then our main data structure consists of a trie with $n$ vertices and auxiliary structures. I want to ...
- 151
1
vote
1
answer
300
views
The last failure link in KMP automaton
I know that in order to build i's failure link, I compare i's and j's success links:
If they are the same (if a = b), then i's failure link should point to state j + 1.
If they aren't the same, we go ...
- 385