Algorithm for an extended version of string matching

Question

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

Abhishek Bansal · Accepted Answer · 2013-10-17 09:30:18Z

1

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

edited Oct 17, 2013 at 9:30

answered Oct 17, 2013 at 9:25

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

LostAvatar · Accepted Answer · 2013-10-17 09:32:41Z

0

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.

edited Oct 17, 2013 at 9:32

answered Oct 17, 2013 at 9:26

LostAvatar

7947 silver badges20 bronze badges

Collectives™ on Stack Overflow

Algorithm for an extended version of string matching

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related