Christmas Challenge - Week Code 27 - How many substrings?

Dec. 25, 2016

Problem statement:

https://www.hackerrank.com/contests/w27/challenges/how-many-substrings

Advanced algorithm

Maximum score 100

Julia likes to work on the string problem, she likes to do some research before she write code.

She chooses to use dynamic programming, memorization tactics. Also, she is looking into the data structure -

http://www.cs.jhu.edu/~langmea/resources/lecture_notes/tries_and_suffix_tries.pdf

Trie, Suffix Tree, Suffix Array, FM Index

She likes to design the algorithm, avoid timeout, out-of-space issue. And she planed to go to a Christmas party by skytrain to Surrey, she has to have a nice dinner with over 30 people.

Now it is 12:15pm - 6pm, she likes to make some good points on this contest. Now, she is ranking 2230/ 6000.

http://stackoverflow.com/questions/6416050/how-to-create-a-trie-in-c-sharp

http://stackoverflow.com/questions/6022848/how-to-find-a-word-from-arrays-of-characters/6073004#6073004

Google
bloom filter/ scrabble algorithm/ ...

Julia, do not make things too difficult. Use string search, DP, memorization
Work out a simple example,

Simplify - Make a few points first 

For example, suppose that abcdef, there are how many substrings:

string length = 1, there are 6, a, b, c, d, e, f
string length = 2, start position from 0 to 4, total is 5
string length = 3, start position from 0 to 3, total is 4
string length = 4, start position from 0 to 2, total is 3
string length = 5, start position from 0 to 1, total is 2
string length = 6, start position from 0, total is 1

And then, next, using dynamic programming, memorization - space is too big.
string "abcdef", S(N), N = 6, S(N) = 6 + 5 + 4 + 3 + 2 + 1 = 21
add one more char, "abcdef" + "g", so, possible new substrings:
abcdefg
bcdefg
cdefg
defg
efg
fg
g

What I need to do is to search the possible substring through the original string: "abcdef",
now, it turns to a substring search problem.

KMP, Rabin search, ....
http://juliachencoding.blogspot.ca/2016/09/hackerrank-stryker-code-sprint-grind_3.html

Scored 50 of maximum score 100.
subtasks:
For 30% of the cases, 1 <= n, q <= 100
For 50% of the cases, 1 <= n, q <= 3000
For 100% of the test case, 1 <=n, q <= 100000

Rank:  996 (From 7260),   top 20% - Very good! stop here and go to Christmas party! (5:10pm)

Blog reading:
1. http://www3.cs.stonybrook.edu/~rezaul/ACM-ICPC/GNY-2015/regional-2015.html

2. https://www.hackerrank.com/syuxuan