patternModerate
Algorithm to search substring in a circular string?
Viewed 0 times
searchsubstringalgorithmcircularstring
Problem
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.
An source/query example that should succeed:
Do you know of any references on substring search on circular strings? Any advice on how to do this?
(Possibly) related:
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 DABCAn source/query example that should succeed:
Source string: EFxxxABCxxxxxD
Query string: DEFDo you know of any references on substring search on circular strings? Any advice on how to do this?
(Possibly) related:
- CS: Automaton for substring matching
- SO: main differences between the KMP and BM algorithms?
- http://en.wikipedia.org/wiki/String_searching_algorithm
Solution
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.
Then perform a simple (non-circular) search on that temporary string.
Context
StackExchange Computer Science Q#42609, answer score: 10
Revisions (0)
No revisions yet.