Longest Common Prefix - using Trie

Sept. 7, 2016

Work on C# practice:
http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/

One of longest common prefix series:
1. http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/
2. http://www.geeksforgeeks.org/longest-common-prefix-set-2-character-by-character-matching/
3. http://www.geeksforgeeks.org/longest-common-prefix-set-3-divide-and-conquer/
4. http://www.geeksforgeeks.org/longest-common-prefix-set-4-binary-search/
5. http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/

Will work on coding very soon.

C# practice:
https://gist.github.com/jianminchen/d65887908a16e1c12d708a2912c4c081

Add time complexity and auxiliary space detail:
Time Complexity : Inserting all the words in the trie takes O(MN) time and performing a walk on the trie takes O(M) time, where-

N = Number of strings

M = Length of the largest string string

Auxiliary Space: To store all the strings we need to allocate O(26MN) ~ O(MN) space for the Trie.

From the website:

http://www.geeksforgeeks.org/longest-common-prefix-set-5-using-trie/

Editorial Notes:

1. This is the first C# implementation of Trie Julia wrote.

2. How does she get here?

HackerRank code sprint #6 has an algorithm related to suffix array ->

continue to work on suffix array ->

Longest common prefix ->

string search speed up ->

found a 5 solution series on geeksforgeeks ->

work on 5th solution, Trie, LCP

3. Prior experience worked on suffix array:

http://juliachencoding.blogspot.ca/2016/04/april-11-2016-plan-to-work-on-lcp-array.html
http://juliachencoding.blogspot.ca/2016/04/april-11-2016-plan-to-work-on-lcp-array.html

Try to solve the advanced problem again after 5 month (April, 2016) using suffix array, LCP, two pointer technique:
https://www.hackerrank.com/challenges/string-function-calculation

Suffix Array and longest common prefix array (LCP array) - study

June 5, 2016

 It is the labor day long weekend, spent 3 hours (6:30am - 10:00am) to read suffix array from this favorite competitive programming book, and try to please herself, a new goal - score any point with suffix array work or LCP (even cannot remember the full name - called longest common prefix array), HackerRank practice or code sprint.

It is a lonely journey - reading the book, but it is perfect for physical recovery  - muscle and bones -
laying on the bed with the excellent one night sleep, just after 3+ hour tennis sports, and do not want to move, read a book.

Yesterday, Julia warmed up more than 1+ hour, one single match, one double match lasted more than one hour, until tie break. She lost double with 5 to 7 lost the match.  She suffered tennis elbow pain issues.

The competitive book about suffix array:

6.4 Suffix Tree and Suffix Array - page 114 - 119


Motivation talk
1. suffix array - who did the research to introduce the term - suffix array in 1993?

 https://en.wikipedia.org/wiki/LCP_array
 https://en.wikipedia.org/wiki/Udi_Manber

More reading:
Suffix array:
http://algs4.cs.princeton.edu/63suffix/

Play with some code first, get solid understanding suffix array - what are the benefits using suffix array? Shorten time complexity - 

suffix tree -> suffix array -> sorted array -> LCP - longest common prefix

Arguments:
1. Building efficient Suffix Tree under contest environment is a bit complex and risky
2. Suffix Array invented by Udi Manber and Gene Myers, has similar functionalities as Suffix Tree but simpler to implement, especially in programming contest setting
3. ...

Facts:
1. Suffix Array is an integer array that contains indices of sorted suffixes


1. Write C# version of this Java code:
http://algs4.cs.princeton.edu/63suffix/SuffixArray.java.html

2. Suffix array - longest repeated substring - using suffix array
http://algs4.cs.princeton.edu/63suffix/LongestRepeatedSubstring.java.html

3. Keyword in context (KWIC)
Given the suffix array, easy to search for a string or sentence via binary search. Memory is linear. Search is O(K log N) where K is the length of the string you are searching for. (Can be done in K + log N by using the lcp array.)

study the code:

More reading:
1. https://leetcode.com/articles/longest-common-prefix/

2. http://www.geeksforgeeks.org/longest-common-prefix-set-1-word-by-word-matching/
3. http://www.geeksforgeeks.org/longest-common-prefix-set-2-character-by-character-matching/
4. http://www.geeksforgeeks.org/longest-common-prefix-set-3-divide-and-conquer/
5. http://www.geeksforgeeks.org/longest-common-prefix-set-4-binary-search/

- Julia likes to calm down quickly when she gets nervous. When she has a negative self-talk, she will remind herself - "Everyone faces challenges on court and I'm no different." Replace with positive self-talk.

Everyone faces challenges on court and I’m no different. Get out on court and overcome yours to #CreateYourMark pic.twitter.com/RSNn7AqFch

— Ana Ivanovic (@AnaIvanovic) May 21, 2016

HackerRank: String Calculate function (III) - Suffix array (II)

April 11, 2016
Problem statement:

https://www.hackerrank.com/challenges/string-function-calcula

Plan to work on LCP array later. 

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

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

SuffixArray implemented in C#, by MSFT, Google employee; Julia has to catch up C#, and learn 

how to write beautiful code like this:

Study C# code how to implement IEnumberable interface in suffixArray code:

https://msdn.microsoft.com/en-us/library/system.collections.ienumerable(v=vs.110).aspx

how String.Compare api is designed

https://msdn.microsoft.com/en-us/library/x7tax739(v=vs.110).aspx 

Julia also takes some time to work on suffix array, and get some drawing about suffix tree, and play with two case:

aaaaaa, 
banana, 

abcabcddd, 

For those two strings, what are suffix tree? Get so close to concrete examples, draw diagram, run test case, study code, and compare to other C# submission. 

Focus on how to find the range of suffix array to fit in the pattern: 

https://gist.github.com/jianminchen/700ebc3150efdd9ac33ac75f56f727d3

Walk through the examples how suffix array is implemented in C# code:

public SuffixArray Search(string str)

{

if (m_lower > m_upper)

return this;

// Otherwise search for boundaries that enclose all

// suffixes that start with supplied string.

var lower = Search(str, c_lower);

var upper = Search(str, c_upper);

return new SuffixArray(m_text, m_pos, lower + 1, upper);

}

Example 1: string "aaaaaa", pattern string "aaa". 

suffix array {5, 4, 3, 2, 1, 0}

suffix string:

a

aa

aaa

aaaa

aaaaa

aaaaaa

suffix array is acending order, string.Compare("a","aa")  = -1, string.Compare("aa","aa") = 0. string.Compare("aa","a") = 1

suffix array is implemented using interface IEnumberable. 

we try to find 2 index, low, top, 

index = 1, "aa", string.compare("aa", 0,"aaa",0, 3) = -1, 

now, we need to find top index, 

assume that "abc" is in the array, string.compare("abc",0,"aaa",0, 3) = 1, first one is >-1, stop; 

aaa, aaaa, aaaaa, aaaaa, all computed value of comparison = 0 since we only check substring with length 3. 

So top index is 5. 

So, count of substring "aaa" is calculate by top index - low index + 1

top index = 5, 

low index = 1+1

so count = 4. 

Try to figure out how this binary search algorithm is used to calculate low index and top index, called twice, comparison value for low index = 0, for high index is -1. 

In other words, find last one is smaller than "aaa", and first one bigger than "aaa". 

Example 2: "banana", pattern "ban", 

 Read the content in the blog first:

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

And then, 
suffix strings:
banana
anana
nana
ana
na
a

Sort them ascending order:
a
ana
anana
banna
na
nana

pattern string "ban", first to find a string which is last one < "ban", -> "anana", index 2, "ana" < "ban"
and then, find first string which is bigger than "ban", only comparing length 3 substring, 
"banna" = "ban" based on comparison (substring len = 3), so
"na" - index = 4 > "ban"
2+1 = 3, 
top index = 3 
so, ban pattern match is  3-3 +1 = 1

"Work on Examples First" - Practice feels good!

The LCP-LR array helps improve this to O(m+logN)O(m+logN), in the following way

LCP array reading

https://www.hackerrank.com/challenges/pseudo-isomorphic-substrings/topics/lcp-array

https://en.wikipedia.org/wiki/LCP_array

Follow up: May 4, 2015

Read the article:

http://stackoverflow.com/questions/2487576/trie-vs-suffix-tree-vs-suffix-array

June 10, 2016 - Plan to spend 30 minutes to read the slides:

Julia, learn something here from the blog:

http://decomplexify.blogspot.ca/

http://decomplexify.blogspot.ca/2014/06/suffix-array.html

http://decomplexify.blogspot.ca/2014/07/lcp-array.html?view=classic