Need help with the question.

[MyCreativityDiedWithEngg]

You are given a String of length N. You have to make an array A of length N such that A[i] indicates the max common prefix length of the original string and the substring S[i...N]. N can be as large as 100000.

For example,
S= ababa

A=[5,0,3,0,1]

[salem c]

So what have you done so far?

With no demonstration of effort on your part, your "help with question" looks a lot like "Will you write this for me so I can go to the party/beach/cinema instead".

[MyCreativityDiedWithEngg]

Till now I have tried Brute force algorithm and it is giving timelimit.

You all can just give me the hint from where to start.

[mbozzi]

If I had to guess, you already understand how to solve your original problem (well, at least you found a hint), because this problem is equivalent and nobody discusses LCP without mentioning suffix arrays.

Why not continue this in your other thread?
http://www.cplusplus.com/forum/general/246072/

[MyCreativityDiedWithEngg]

Nope I did not find a way for my previous problem

[mbozzi]

Go read about suffix trees. A suffix tree is actually a kind of radix tree (or trie) containing all the suffixes of a particular string. About books, CLRS treats tries briefly, but doesn't talk about suffix trees in particular. You might have better luck searching the web.

The longest common prefix (LCP) problem is solvable in constant time after linear effort building an augmented suffix tree. It is related to the other question in the following way:

Given S = "ababaab" and nonempty suffixes s0 = "ababaab", s1 = "babaab", s2 = "abaab", ..., then
lcp(S, s0) = 7, implying that the first (all) 7 nonempty prefixes of s0 are common with the prefix of S;
lcp(S, s1) = 0, implying that s1 and S have no common prefixes;
lcp(S, s2) = 3, implying that s2 and S have 3 common prefixes - "aba", "ab", and "a", and so on.

You'd just compute this for every si and then multiply, as far as I can tell.

Actually a suffix tree is not required - I think it's easier to understand that the problem is looking for the depth of the lowest-common-ancestor in a suffix tree, but one can get the answer with RMQ directly from the suffix array:
https://en.wikipedia.org/wiki/LCP_array#LCP_queries_for_arbitrary_suffixes

I suppose it's a bit off topic but one observation about the other problem is that you have a tremendous number of queries but only one document, so you probably need to pre-process the document rather than the queries. This generally hints at a data-structure based solution.