Questions tagged [exact-string-matching]
The exact-string-matching tag has no usage guidance.
25
questions
1
vote
0
answers
40
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 ...
- 431
0
votes
0
answers
14
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
123
views
Failure function of the Fibonacci strings (The Dragon Book Exercise 3.4.9d)
Exercise 3.4.9 of The Dragon Book defines Fibonacci strings as follows:
$s_1 = b$.
$s_2 = a$.
$s_k = s_{k-1}s_{k-2}$ for $k>2$.
Part (d) then poses the following question:
Show that the failure ...
- 13
2
votes
3
answers
327
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
3
votes
1
answer
68
views
Why does the exact string matching brute force algorithm not compare index 1 of P with index 1 of S in the first round of the for?
In my ADS course we were given this pseudo code for the "exact string matching brute force" algorithm:
...
- 151
2
votes
0
answers
84
views
How to build a minimal string matching DFA with limited memory?
I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
- 876
2
votes
1
answer
127
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 ...
- 123
1
vote
1
answer
107
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 \...
- 133
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
...
- 113
2
votes
1
answer
110
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-...
2
votes
1
answer
99
views
Is there any neutral element for the cryptographic hash function SHA256? (or its variants)
My question is the following:
Is it possible to compute a string given that after applying a SHA256 function the result is the same string?
Edit for clarification:
If my string A is a neutral element ...
- 21
1
vote
0
answers
149
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
2
answers
131
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 ...
- 227
1
vote
0
answers
24
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
0
answers
77
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 ...
- 131
7
votes
0
answers
1k
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 ...
- 179
7
votes
3
answers
8k
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$...
- 275
4
votes
1
answer
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 ...
- 143
1
vote
1
answer
1k
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: ...
- 141
4
votes
4
answers
2k
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 ...
- 41
6
votes
1
answer
3k
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" ...
- 411
7
votes
1
answer
2k
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 ...
- 73
1
vote
0
answers
62
views
Why is the second while loop in KMP not a conditional statement?
When building the partial match table for KMP:
...
0
votes
0
answers
153
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 ...
- 239
0
votes
1
answer
228
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 ...
- 260