I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt.
However, as far as I understand, these operate on "regular" strings, but what I need is a substring search on a circular string.
A circular string as a string characterized only by its size and the order of the elements, i.e. ABCD
is the same as BCDA
, CDAB
and DABC
An source/query example that should succeed:
Source string: EFxxxABCxxxxxD
Query string: DEF
Do you know of any references on substring search on circular strings? Any advice on how to do this?
(Possibly) related:
it might be worth compiling it
? At present, I implemented what @Marc-Johnston suggested, seams to work but I haven't done extensive tests by now. $\endgroup$you mean that the source string is always larger than the query string
: yes. $\endgroup$