4
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – babou May 18 '15 at 17:04
  • $\begingroup$ @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. $\endgroup$ – kebs May 18 '15 at 17:05
  • $\begingroup$ 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. $\endgroup$ – babou May 18 '15 at 17:28
  • $\begingroup$ When you reply "Q1: no", you mean that the source string is always larger than the query string? right? $\endgroup$ – babou May 18 '15 at 17:30
  • $\begingroup$ you mean that the source string is always larger than the query string: yes. $\endgroup$ – kebs May 18 '15 at 17:32
7
$\begingroup$

Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string. The source string must be concatenated at least once.

Then perform a simple (non-circular) search on that temporary string.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bryce Sandlund May 15 '15 at 18:43
  • $\begingroup$ Agreed ... this algorithm is pretty much O(n + m) ... although a binary search tree may be able to make it O(log n + m) $\endgroup$ – Marc Johnston May 15 '15 at 19:02
  • $\begingroup$ I updated the algorithm to denote a minimum of 1 concatenation is required. $\endgroup$ – Marc Johnston May 16 '15 at 1:02
  • $\begingroup$ Also note this ... the circular problem is really solved only with the concatenation step. Then the problem becomes an algorithm for substring searching. To truly improve the big O for the original problem, the concatenation algorithm needs to be improved, not the substring search. $\endgroup$ – Marc Johnston May 16 '15 at 1:05
  • 1
    $\begingroup$ I thought about it a little bit... And really the source string only has to be n + m - 1 in length ... doubling the source string in length each time would be wasteful... n+m-1 would be the least amount of characters ... which reduces the search string length $\endgroup$ – Marc Johnston May 16 '15 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.