Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
1 vote
1 answer
36 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. ...
user169664's user avatar
1 vote
1 answer
78 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 ...
Tigerion's user avatar
0 votes
0 answers
19 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 ...
Toothpick Anemone's user avatar
0 votes
0 answers
26 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 ...
Iridescent 53's user avatar
1 vote
0 answers
43 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 ...
chubakueno's user avatar
0 votes
0 answers
20 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 ...
Quiescent's user avatar
  • 101
1 vote
1 answer
72 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 ...
Mathguy's user avatar
  • 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. ...
Toothpick Anemone's user avatar
0 votes
1 answer
79 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: ...
AsukaMinato's user avatar
0 votes
1 answer
209 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$,...
Mikey's user avatar
  • 3
2 votes
1 answer
333 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 ...
giofrida's user avatar
  • 183
2 votes
1 answer
72 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 ...
giofrida's user avatar
  • 183
1 vote
1 answer
36 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, ...
ccleve's user avatar
  • 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, ...
Toothpick Anemone's user avatar
0 votes
0 answers
32 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}...
ishandutta2007's user avatar
2 votes
3 answers
461 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 ...
Enlico's user avatar
  • 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}^*...
Mohamad S.'s user avatar
1 vote
0 answers
60 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 ...
Sridhar Ratnakumar's user avatar
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 ...
Nave Tseva's user avatar
1 vote
1 answer
330 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$ ...
Conway's user avatar
  • 41
4 votes
1 answer
473 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 ...
B_math's user avatar
  • 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 ...
Gunther Schadow's user avatar
0 votes
0 answers
62 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 ...
Jimmy's user avatar
  • 29
0 votes
1 answer
47 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 ...
asharpharp's user avatar
1 vote
0 answers
93 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 ...
Sharingan's user avatar
1 vote
1 answer
179 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 ...
Quade's user avatar
  • 111
3 votes
1 answer
975 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 ...
maxbachmann's user avatar
1 vote
1 answer
113 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 \...
alan's user avatar
  • 133
0 votes
1 answer
34 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 ...
Salwa's user avatar
  • 131
0 votes
2 answers
270 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. ...
Rockstar5645's user avatar
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 ...
SpiritBob's 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: ...
Tenders McChiken's user avatar
2 votes
1 answer
332 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 ...
Eli Zatlawy's user avatar
2 votes
1 answer
134 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-...
Suminda Sirinath S. Dharmasena's user avatar
1 vote
0 answers
473 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 ...
PsychoKitten's user avatar
2 votes
1 answer
148 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 ...
Ewin Zuo's user avatar
3 votes
0 answers
190 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 ...
Philip Müller's user avatar
2 votes
0 answers
81 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 ...
user9041346's user avatar
1 vote
2 answers
63 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 ...
Anon Coward's user avatar
2 votes
0 answers
108 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 ...
Silver Flash's user avatar
0 votes
2 answers
149 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 ...
Toothpick Anemone's user avatar
8 votes
3 answers
11k 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 ...
jtschoonhoven's user avatar
0 votes
0 answers
62 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 ...
BlackOnyx's user avatar
4 votes
3 answers
362 views

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

We get two arrays: ordering = ["one", "two", "three"] and ...
Pe Wu's user avatar
  • 143
3 votes
1 answer
807 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 ...
securitymensch's user avatar
1 vote
2 answers
241 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 ...
ljleb's user avatar
  • 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 ...
mcqueenvh's user avatar
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 ...
therealak12's user avatar
6 votes
1 answer
234 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 ...
mookid's user avatar
  • 169
1 vote
0 answers
40 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 ...
flowit's user avatar
  • 111