Questions tagged [exact-string-matching]
The exact-string-matching tag has no usage guidance.
13
questions
2
votes
2answers
90 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
19 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
42 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 ...
5
votes
0answers
493 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
3k 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
982 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
263 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
680 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
42 views
Why is the second while loop in KMP not a conditional statement?
When building the partial match table for KMP:
...
0
votes
0answers
75 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
148 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) ...
