CODEWITHSUNDEEP
algorithmstring-matching
user9343456
user9343456

Reputation: 351

Algorithm for an extended version of string matching

I recently studied about string matching, and was inspired to think of a similar problem. Let p be a string of m characters and t be a text of n characters. Now the problem is to find out if p occurs in t in the following way: there exists an i in the range [0, n-1] such that:

p[ j ] = t [ i + j ] for j = 0, 1, ... ,m - 1,

where i + j is computed modulo n. As an example, in normal string matching, ABCD would not occur in CDEFAB, but you can see that in the above-defined problem, ABCD would occur in CDEFAB, i = 4 in this case.

Is there any linear-time algorithm to determine if a pattern p occurs in t? And has this problem been treated before?

Thanks in advance

Upvotes: 1

Views: 99

Answers (2)

LostAvatar
LostAvatar

Reputation: 794

Just double t and make an ordinary lookup for p?

So you would look up ABCD in CDEFABCDEFAB and would get the right i. That can be made in linear time.

Upvotes: 0

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

I think you can still apply the linear time KMP algorithm to solve it. Just add m-1 characters t[0], t1,...,t[m-2] to the end of the text t. Ofcourse you only need to do this if you still have a candidate substring left in your table after the text t ends.

If test string is BCDEA
AXYZBCDE shall become AXYZBCDEAXYZ

Upvotes: 1

Related Questions