Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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)

3
votes
1answer
62 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
39 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
58 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
31 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
50 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
159 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
96 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
104 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
382 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
11 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
52 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
48 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
60 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 ...
0
votes
0answers
44 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 ...
3
votes
2answers
154 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 ...