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:

http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/

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. 

Read suffix array blog, play with code first:

http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/

http://www.geeksforgeeks.org/suffix-array-set-1-introduction/

here is the suffix array submission: 

https://www.hackerrank.com/rest/contests/master/challenges/string-function-calculation/hackers/oguzhaneker/download_solution

read C# suffixArray implementation:

https://github.com/eranmeir/Sufa-Suffix-Array-Csharp/blob/master/Sufa/SuffixArray.cs

one more reading (blog #1):

https://blogs.msdn.microsoft.com/dhuba/2010/04/04/suffix-array/

Use C# implementation of suffix array in blog #1, still time out on hackerRank

https://gist.github.com/jianminchen/0f561b8afc1cdf23ab95a8b603cd2a3e

Plan to work on LCP array later, solve timeout issue.