The Stack Overflow podcast is back! Listen to an interview with our new CEO.

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
0answers
31 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-...
6
votes
1answer
583 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
35 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
15 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 ...
0
votes
0answers
41 views

Is there an algorithm to compress a string array represented as pointers to a long string to pointers with a compressed version of the long string?

In a program I am writing, I represent an array of strings as a long string and have pointers point at the various substrings to present my array. E.g. ...
-1
votes
2answers
41 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
34 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
84 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
0answers
29 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
33 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
45 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
57 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
65 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
109 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
157 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 ...
1
vote
1answer
1k 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
78 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
79 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
412 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
229 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 ...
0
votes
3answers
341 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
441 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
72 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
54 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
53 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
106 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
187 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 ...