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
2 votes
3 answers
82 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 ...
user avatar
  • 73
1 vote
1 answer
38 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}^*...
user avatar
0 votes
0 answers
36 views

How do right contexts work in context-sensitive L-Systems?

I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
1 vote
0 answers
30 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 ...
user avatar
0 votes
0 answers
25 views

Finding matches between an input string and a fixed set of strings

I need to compare an input string to multiple strings which I'll refer to as fixed strings, and you can assume the latter won't change. Comparison disregards letters with special characters, only ...
user avatar
  • 158
1 vote
1 answer
64 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$ ...
user avatar
  • 39
4 votes
1 answer
81 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 ...
user avatar
  • 39
1 vote
0 answers
27 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 ...
user avatar
0 votes
0 answers
20 views

question about common prefix of Strings

we are given n Strings of total Length K and also we have m queries about these strings. each query, contains 2 index ( for example a , b ) and then we should calculate the length of longest common ...
user avatar
  • 1
0 votes
0 answers
50 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 ...
user avatar
  • 29
0 votes
1 answer
32 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 ...
user avatar
1 vote
0 answers
50 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 ...
user avatar
1 vote
1 answer
70 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 ...
user avatar
  • 111
2 votes
1 answer
250 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 ...
user avatar
1 vote
1 answer
42 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 \...
user avatar
  • 133
0 votes
1 answer
27 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 ...
user avatar
  • 131
0 votes
2 answers
129 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. ...
user avatar
1 vote
1 answer
326 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 ...
user avatar
  • 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: ...
user avatar
2 votes
1 answer
220 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 ...
user avatar
  • 165
2 votes
1 answer
69 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-...
user avatar
1 vote
0 answers
164 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 ...
user avatar
2 votes
1 answer
74 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 ...
user avatar
2 votes
0 answers
79 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 ...
user avatar
2 votes
0 answers
27 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 ...
user avatar
1 vote
1 answer
40 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 ...
user avatar
2 votes
0 answers
50 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 ...
user avatar
0 votes
2 answers
105 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 ...
user avatar
7 votes
3 answers
5k 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 ...
user avatar
0 votes
0 answers
30 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 ...
user avatar
3 votes
3 answers
259 views

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

We get two arrays: ordering = ["one", "two", "three"] and ...
user avatar
  • 131
3 votes
1 answer
310 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 ...
user avatar
1 vote
2 answers
210 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 ...
user avatar
  • 38
3 votes
1 answer
1k 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 ...
user avatar
1 vote
1 answer
740 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 ...
user avatar
5 votes
1 answer
153 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 ...
user avatar
  • 159
1 vote
0 answers
27 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 ...
user avatar
  • 111
1 vote
0 answers
59 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-...
user avatar
  • 21
7 votes
1 answer
731 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 $...
user avatar
2 votes
1 answer
247 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: ...
user avatar
1 vote
0 answers
35 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 ...
user avatar
  • 11
-1 votes
2 answers
96 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, ...
user avatar
0 votes
1 answer
47 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 ...
user avatar
  • 185
2 votes
2 answers
107 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 ...
user avatar
0 votes
1 answer
35 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 ...
user avatar
  • 143
0 votes
1 answer
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.
user avatar
  • 345
1 vote
1 answer
125 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 ...
user avatar
0 votes
0 answers
224 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 ...
user avatar
0 votes
0 answers
126 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 ...
user avatar