String matching algorithm design

Question

Given a text t[1...n] and k pattern p1,p2,...pk each of length m, n=2m, from alphabet [0, Sigma-1]. Design an efficient algorithm to find all locations i in t where any of the patterns pj's match.

So I have a string t = "1 2 3 4 5 2 2 9" and the pattern p = "4 5 2 2". I know there will be m+1 locations I can find a pattern (either from "1 2 3 4", "2 3 4 5", etc...).

Then we have k characters in the pattern so the bigO comes outs to be O(k(m+1)).

My algorithm would be to search through the string checking each character with the characters in the pattern. That will run me k iterations for m+1 locations.

Hopefully, I'm explaining it correctly. I just want to know if I'm doing it right and if there are any flaws in my logic. Thank you!

Multiple patterns. Is this en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm? — mcdowella
– mcdowella, Commented Mar 31, 2016 at 4:23

HenryLee · Accepted Answer · 2016-03-31 03:33:49Z

1

My algorithm would be to search through the string checking each character with the characters in the pattern. That will run me k iterations for m+1 locations.

That means for each pattern, you can do it O(m+1), right?

Although there are algorithms that can achieve this performance, your brute force one isn't. You have m+1 locations, and for each location you need to check m characters, so the total complexity for each pattern is O(m(m+1)).

answered Mar 31, 2016 at 3:33

HenryLee

4063 silver badges9 bronze badges

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

6 Comments

o.o Over a year ago

I'm a little lost on what you mean with your question. I am not trying to achieve O(m+1), rather O(k(m+1)) or O(m(m+1)) (same thing basically). Are you saying my brute force way would not be O(k(m+1))?

HenryLee Over a year ago

@m.o I mean for each pattern it's O(m(m+1)), you have k patterns, the total would O(k(m(m+1))). So O(k(m+1)) is not achievable in brute force.

o.o Over a year ago

Oh, I see. Can you help me understand how I would achieve O(k(m+1))? I don't know how else I can do this.

HenryLee Over a year ago

@m.o I suggest you start with the KMP algorithm, for each pattern of length m and a text of length n, the worst matching complexity is O(n). en.wikipedia.org/wiki/…

HenryLee Over a year ago

@m.o And none of the efficient string matching algorithms can be described in a few words. So take your time on some reading. en.wikipedia.org/wiki/String_searching_algorithm

|

Collectives™ on Stack Overflow

String matching algorithm design

1 Answer 1

6 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Related