Questions tagged [exact-string-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
2answers
83 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
36 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 ...
2
votes
0answers
393 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
895 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
240 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
966 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
648 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
41 views

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

When building the partial match table for KMP: ...
0
votes
0answers
65 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
140 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) ...