Sunday, April 10, 2016

HackerRank: String Calculate function (III) - Suffix array

April 10, 2016

Time spent: 9:00pm - 11:40pm

Problem statement - string calculate function on Hackerrank 

KMP Algorithm, Rabin Karp Algorithm, Finite Automate based Algorithm, Boyer Moore algorthm. 

All of the above algorithms preprocess the pattern to make the pattern searching faster. The best time complexity that we could get by preprocessing pattern is O( n ) where n is length of the text. 

So, Julia second try still failed, no progress on time out issue. 

Now, Julia read the blog and learn suffix array / LCP array in next hour 9:00 pm -10:00 pm:

A suffix tree is built of the text. After preprocessing text (building suffix tree of text), we can search any pattern in O(m) time where m is length of the pattern. O(n) -> O(m), solve timeout issue

No comments:

Post a Comment