XLR8ST's blog

Number of different substrings of a string

By XLR8ST, 9 years ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How much have you have complexity?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it -11 Vote: I do not like it

              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 .

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                ← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

                → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How ? Can you explain using code ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i am very intresting in it.

        → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like 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:

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<int> z = z_function( x );
    //this work too
    //vector<int> z = prefix_functionx(x); 
    int mx = 0;
    foreach j to x.size()-1
        mx = max( mx , z[j] );
    sol += (i+1) - mx; 

cout << sol;
→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply