Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

XLR8ST's blog

Number of different substrings of a string

By XLR8ST, 11 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 (13)
| Write comment?
»
11 years ago, hide # |
 
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
  • »
    »
    11 years ago, hide # ^ |
     
    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
    • »
      »
      »
      11 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        11 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        How much have you have complexity?

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, hide # ^ |
           
          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
          • »
            »
            »
            »
            »
            »
            11 years ago, hide # ^ |
             
            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
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, hide # ^ |
               
              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
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, hide # ^ |
                ← 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
  • »
    »
    11 years ago, hide # ^ |
     
    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, hide # |
 
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
»
4 years ago, hide # |
← 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