# Algorithm to search substring in a circular string?

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:

• Do you have more details about the problem? Can the circular string contain less elements than the substring pattern? Do you use the same pattern repeatedly so that it might be worth compiling it (as in Boyer-Moore or KMP)? – babou May 18 '15 at 17:04
• @babou Q1: no, Q2: I don't understand, what do you mean by 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. – kebs May 18 '15 at 17:05
• I guess my question may not be properly stated. If you consider the KMP algorithm, there is a cost in building the table, which is O(m), m being the query string size. If the same query string is used many times, then this cost may be ignored as it is amortized on many queries. In that case, considering the cost on concatenating small loops makes sense in assessing complexity. But if you include the table creation in the cost, then the discussion on concatenation cost is pretty much pointless. I am working on how to avoid most of the concatenation, hence the question. – babou May 18 '15 at 17:28
• When you reply "Q1: no", you mean that the source string is always larger than the query string? right? – babou May 18 '15 at 17:30
• you mean that the source string is always larger than the query string: yes. – kebs May 18 '15 at 17:32

• If the source string is of length $n$ and the query string of length $m$, then this algorithm is $O(n + m)$ if KMP is run on the resulting instance, which is the same complexity as KMP on a noncircular string, which is optimal. Though you should duplicate the string until it has at least $n + m - 1$ characters, as @keb's example shows. – Bryce Sandlund May 15 '15 at 18:43