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)

77 questions
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. ...
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 ...
• 11
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 ...
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 ...
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 ...
• 441
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 ...
• 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 ...
• 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
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: ...
• 193
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$,...
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 ...
• 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 ...
• 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, ...
• 129
0 votes
0 answers
61 views

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 ...
• 73
1 vote
1 answer
63 views

• 115
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 ...
• 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 ...
• 111