### XLR8ST's blog

By XLR8ST, 9 years ago,

How can i find the no. of distinct substrings of a string using Z-FUNCTION/Z-ARRAY ?

Time complexity should be less than O(n2).

I know there is a way using suffix array but i am more interested in solving this using Z-array/Z-function.

• +1

| Write comment?
 » 9 years ago, # |   +3 Let Z[i] be the Z-value array of the suffix of S starting at position i. Then, for each position k, compute maxZ[k], the maximum of Z[0][k], Z[1][k-1], Z[2][k-2], ..., Z[k-1][1] (the maximum prefix of S[k..n) that also occurs in some earlier prefix of S). Then, all substrings starting at position k of length up to maxZ[k] have already occurred so you do not want to count those, but you count all longer substrings. Therefore, the answer is sum{k=0 to n} (n — k — maxZ[k]).
•  » » 9 years ago, # ^ |   -9 I'm unable to understand you . Why is the Z array 2-d ?
•  » » » 9 years ago, # ^ |   0 Each Z[i] is its own 1D array so Z is a 2D array
•  » » » » 9 years ago, # ^ |   0 How much have you have complexity?
•  » » » » » 9 years ago, # ^ |   0 It's O(n^2) time and space complexity. Here is a link to some Java code for it. You don't actually need to make a 2-D array though. You can just create a new 1-D array in each iteration of the outer for loop which results in O(n) memory.
•  » » » » » » 9 years ago, # ^ |   0 But XLR8ST asked something about less then O(N^2). And this is really interesting. Of course, we have suffix structurers such as suffix tree, but it's intresting to know about something easier than suffix structurers.
•  » » » » » » » 7 years ago, # ^ |   -11 http://ideone.com/hNMki9 this one uses a suffix array (nlogn) construction + LCP array (n) construction. Together they make the overall complexity nlogn. There is also one linear time suffix array calculation approach. If you use SA + LCP approach then you can count no. of distinct substrings in a string in time similar to the construction time of SA + LCP because, after SA + LCP is constructed it takes only linear time to count .
•  » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   -10 prem.kvit you dont have to share your hackerrank solution!! also your solution is wrong
•  » » 9 years ago, # ^ |   -8 you defined Z as 1-dimensional array and after that used them such as 2-dimensional.
•  » » » 9 years ago, # ^ |   0 How ? Can you explain using code ?
•  » » » » 9 years ago, # ^ |   0 i am very intresting in it.
 » 7 years ago, # |   +3 for each prefix i of the word, reverse it and do z_function over it, the number of new distinct substrings that end in the prefix i is (the length of the prefix) — (maximum value in the z_function array) the pseudo code look like this: string s; cin >> s; int sol = 0 foreach i to s.size()-1 string x = s.substr( 0 , i+1 ); reverse( x.begin() , x.end() ); vector z = z_function( x ); //this work too //vector z = prefix_functionx(x); int mx = 0; foreach j to x.size()-1 mx = max( mx , z[j] ); sol += (i+1) - mx; cout << sol; 
 » 21 month(s) ago, # | ← Rev. 2 →   -20 The following is the wrong algorithm, sorry for this.I guess it is better to use trie data structure that will reduce the time complexity to O(26*N) but it effectively use to give number of distinct substrings as you want to calculate.Code link: https://wtools.io/paste-code/bDox
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 This doesn't look like an O(26*N) solution.PS: this was asked in a recent hiring challenge(over now) and length of string given was 1e5.
•  » » » 7 months ago, # ^ |   0 Did you find the optimised solution?
•  » » » » 7 months ago, # ^ |   0 nope.. learning lcp and suffix array stuffs