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

Time complexity should be less than O(n^{2}).

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

# | User | Rating |
---|---|---|

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | adamant | 164 |

2 | awoo | 164 |

4 | TheScrasse | 160 |

5 | nor | 159 |

6 | maroonrk | 156 |

7 | SecondThread | 150 |

8 | -is-this-fft- | 149 |

9 | pajenegod | 146 |

10 | BledDest | 144 |

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

Time complexity should be less than O(n^{2}).

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

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/14/2024 23:24:49 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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]).

I'm unable to understand you . Why is the Z array 2-d ?

Each Z[i] is its own 1D array so Z is a 2D array

How much have you have complexity?

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.

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.

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 .

prem.kvit you dont have to share your hackerrank solution!! also your solution is wrong

you defined Z as 1-dimensional array and after that used them such as 2-dimensional.

How ? Can you explain using code ?

i am very intresting in it.

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:

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

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.

Did you find the optimised solution?

nope.. learning lcp and suffix array stuffs