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)

Filter by
Sorted by
Tagged with
0
votes
1answer
24 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 ...
0
votes
2answers
37 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. ...
1
vote
1answer
51 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 ...
1
vote
1answer
55 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: ...
2
votes
1answer
141 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 ...
2
votes
1answer
36 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
0answers
28 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 ...
0
votes
0answers
20 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 ...
1
vote
0answers
21 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
0answers
15 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 ...
0
votes
0answers
23 views

All string matches for regular expression [duplicate]

Given a regular expression, the ask is to find all matches in a string, str. Most implementations give longest match only. For example, [\d]* in str "123456", the regex libraries in C++ or ...
1
vote
1answer
29 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 ...
1
vote
0answers
16 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 ...
0
votes
2answers
93 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
3answers
1k 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 ...
0
votes
0answers
23 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 ...
3
votes
3answers
199 views

Sorting array of strings (with repetitions) according to a given ordering

We get two arrays: ordering = ["one", "two", "three"] and ...
3
votes
1answer
128 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
2answers
170 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 ...
2
votes
1answer
562 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 ...
1
vote
1answer
420 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 ...
5
votes
0answers
95 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 ...
1
vote
0answers
22 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 ...
1
vote
0answers
48 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-...
7
votes
1answer
625 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 $...
2
votes
1answer
136 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: ...
1
vote
0answers
23 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 ...
-1
votes
2answers
62 views

Find first occurence of multiple tokens using C++ [closed]

I am using C++03. I have a stream of chars and I need to find the first token from a group of tokens. That is, I need to find the lowest indexed match. Specifically, the stream is just an char array, ...
0
votes
1answer
39 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 ...
2
votes
2answers
97 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 ...
0
votes
1answer
34 views

Conditions for string substitution commutativity

Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b] Also you can assume that a,c≠𝜀 but you ...
0
votes
1answer
41 views

String matching and bioinformatics [closed]

I'm interestd in string-matching, I would like to know recent open problems in string-matching in field of bioinformatics.
1
vote
1answer
89 views

Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

There's this question on LeetCode (link): Given two strings A and B, find the minimum number of times ...
0
votes
0answers
84 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
0answers
96 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 ...
3
votes
1answer
134 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 ...
0
votes
1answer
492 views

Confused about constructing the “failure table” in Knuth-Morris-Pratt algorithm

I'm trying to learn how the "failure table" is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $O(k)$ time (where $k$ is the length of the ...
2
votes
1answer
5k views

KMP - longest palindromic prefix

I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word. I've seen this algorithm used for determining if a word is rotation of ...
2
votes
1answer
168 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: ...
2
votes
1answer
110 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 ...
1
vote
1answer
754 views

A fuzzy string matching algorithm for finding all occurrences from a set of strings in a large string

I have thousands of documents, and a term list with thousands of entries. The entries in the term list range in length from an acronym of two characters to a 14-word phrase with 96 characters. I would ...
1
vote
2answers
486 views

Time complexity of Rabin-Karp algorithm

$n$ : length of text T $m$ : length of pattern P When I study Rabin-Karp algorithm, I learned the best case of this algorithm is $\theta(n-m+1)$. Because if a hashed number is too small to ...
1
vote
3answers
1k views

By what criteria is the base value selected in Rabin Karp algorithm?

In the Rabin Karp algorithm the rolling hash is calculated as follows: H1= c1*a^k-1 + c2*a^k-2+c3*a^k-3+…+ck*a^0 where a is a ...
5
votes
1answer
519 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 ...
1
vote
1answer
279 views

Setting a cutoff for string distance filtering with different length strings

I'm working to filter a table of pairwise names (1.1 M rows) based on string distance algorithms. Most are names, though some are businesses. Edit-based algorithms seem to be best, however in ...
1
vote
1answer
61 views

Why is the Marking Algorithm takes O(number of marks) ?

I am referring to the Marking algorithm defined in this article: https://arxiv.org/pdf/1602.00621.pdf The Marking method is defined at the bottom of page 4 and has a pseudo code at the beginning of ...
0
votes
0answers
56 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 ...
1
vote
1answer
172 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 ...
1
vote
0answers
46 views

Map a set of strings to another set of strings, optimise similarity

Suppose we have a similarity measure s : String x String -> [0, 1] and sets K, L in ...
4
votes
2answers
227 views

NFA models with characters on nodes, not edges

I am attempting to understand the inner workings of the open source string matching library Hyperscan. It takes a multiple-engine approach to the problem of generating string matches, and I'm still ...