Questions tagged [exact-string-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
68 views

Information-theoretic lower bound for succinct string dictionary of the Unicode Name property

Background The literature on succinct data structures refers often to the “information-theoretic lower bound” of encoding data, i.e., the minimum number of bits needed to store the data – a concept ...
1
vote
1answer
26 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 \...
1
vote
1answer
53 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 ...
2
votes
1answer
44 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-...
1
vote
1answer
70 views

Is there any neutral element for the cryptographic hash function SHA256? (or its variants)

My question is Is is possible to compute a string given that after applying a SHA256 function the result is the same string?
1
vote
0answers
76 views

Fastest way to find a substring 'ab' inside a string 'abab'

Let $A$ be an input alphabet - a finite set of symbols. Elements of $A$ are called the characters. The alphabet I am interested in is the set of all ordinary letters ...
2
votes
2answers
101 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 ...
1
vote
0answers
21 views

Estimated vs actual period in Two-Way string search

Both the original paper and all implementations I've seen of the Two Way string search algorithm estimate the period of the needle as $\max(|u|,|v|)$+1 (where $u$ and $v$ are the critical factors). ...
2
votes
0answers
55 views

Bad character rule in the Apostolico–Giancarlo algorithm

In the paper "Tight bounds on the complexity of the Apostoliko-Giancarlo algorithm" by Crochemore and Lecroq authors prove that algorithm performs not more than $1.5n$ comparison of characters in the ...
6
votes
0answers
742 views

Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
5
votes
3answers
5k views

Is there a data structure for efficiently searching a string that contains a given substring?

This question arose from a practical problem: given a set of texts, find one, which contains a given string (not word). Let $S$ be a set of $n$ strings, and $l$ the length of the longest string in $S$...
4
votes
1answer
1k views

Runtime of good suffix table creation in Boyer-Moore algorithm

According to Wikipedia, both bad character table and good suffix table can be created in $O(n)$ time, where $n$ is the length of the pattern. It is pretty obvious how bad character table can be ...
1
vote
1answer
507 views

Horspool's String Search on 0s and 1s

I'm confused in trying to solve the following problem: Find the number of comparisons made by Horspool's string search algorithm in the following case: String: ...
4
votes
4answers
1k views

Substring in a infinite sequence of numbers

I have an infinite sequence of numbers, starting from 1 and need to find position of begin of some given substring of numbers. Example: 1234567891011121314151617181920 ... S = 141 Result: 18 All ...
6
votes
1answer
2k views

String matching algorithm - check if a string matches a pattern

This looks like quite the challenge; given a pattern $P$ (of length $n$) and a string $S$ (of length $m$), how would you check whether the string matches the pattern? For instance: If $P$ = "xyx" ...
7
votes
1answer
1k views

How does the Galil's rule work on Boyer-Moore algorithm?

I would like to know how Boyer-Moore text searching algorithm with Galil's rule works,. I tried to search for but I couldn't understand the information I found, for example this Wikipedia page. And ...
1
vote
0answers
50 views

Why is the second while loop in KMP not a conditional statement?

When building the partial match table for KMP: ...
0
votes
0answers
92 views

Example where overall running time of Boyer-Moore is faster than KMP

Consider the following claim: the pre-processing time of KMP algorithm is more efficient than the pre-processing time of Boyer-Moore algorithm, and the overall running time of KMP is rather more ...
0
votes
1answer
189 views

Question about DFA for exact string matching

In the Handbook of Exact String Matching algorithms, it describes the transition set for a basic string matching automaton as: for q in Q (q is a prefix of x) a in $\Sigma$ (q, a, qa) is in E if and ...