Frez's blog

Xor and String classic problems
By Frez, history, 9 years ago, In English

What's the best algorithms for these below problems?

  • Subarray with Max Xor ?

  • Subsequence with Max Xor ?

  • Longest Subarray among those have Max Xor ?

  • Longest Subsequence among those have Max Xor ?

  • Can we use each algorithm for Min Xor , too ?

  • Longest Common Substring between two strings ?

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

»
9 years ago, # |
  Vote: I like it +39 Vote: I do not like it
  1. Subarray with Max Xor ?
    Bit trie. If you will use array of partial xors , then you are to find . Using bit trie, you can add elements one by one and find one which will give maximum xor with given one.
  2. Subsequence with Max Xor ?
    This is linear algebra problem which can be done with some Gauss elimination if you will maintain basis in correct form.
  3. Longest Subarray among those have Max Xor ?
    Use the algorithm from the first point and for each R you should find the minimum L.
  4. Longest Subsequence among those have Max Xor ?
    I dunno. Is it solvable at all, guys?
  5. Can we use each algorithm for Min Xor , too ?
    Yes.
  6. Longest Common Substring between two strings ?
    Any suffix structure is sufficient. You may take a look at my artice about suffix tree or suffix automaton for example :)
→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

These are the best I know:

So the first problem is just simply a trie of the prefix xors.

Actually I learned the second one just yesterday. Its similar to Gauss Elimination but not the same. I can explain the idea below. It works in O(Nlog(MAX)). Another way to do this is with FFT in O(MAXlog(MAX)log(N)). Note that the second way (with FFT) can be applied if we have a bound for the subset size.

3rd. can be done again with a trie. We just need to find the first occurance of each possible xor.

4th. If you google the first approach for the second problem (max xor subset) and understand it. You should be able to solve this problem. Time complexity again will be O(Nlog(MAX)).

5th. Its the same as for the max.

6th. Again there are a lot of solutions for this problem. The best I know and the easiest to write in my oppinion is using suffix automaton in O(N+M) time.

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

    You misread the 4th one.

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

      Ops, you are right.

      Then you should be able to apply the second method (with FFT). First we find the Maximum xor of a subsequence. Then we will apply a binary search on the maximum length. Then the complexity will be O(MAX * log(MAX) * log^2(N)).

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        Edit: Never mind. That was a silly question. I understood now. Nice comment. :)

        Then we will apply a binary search on the maximum length.

        How did you prove that the length of the max XOR is a linear increasing function?

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

    How to do this with FFT?

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

      So it isn't the straight forward FFT. It is a slight modification of it.

      In the default FFT multiplication if we have polynomials A and B (lets represent the ith coefficient of a polynomial with A[i] or B[i]) we will have RESULT[i+j] = SUM(A[i]*B[j]). In this modification we will have RESULT[i XOR j] = SUM(A[i]*B[j]) — we won't sum the powers but we will xor them.

      Now lets represent our input array as an polynomial. We should count the number of occurrences of every element of the input. Then our polynomial should look something like that:

      A(x) = CNT[0] * x^0 + CNT[1] * x^1 + ... + CNT[MAX] * x ^ MAX

      Lets find Kth power of A(x). In this new polynomial the coefficient before x will be the number of subsets with xor equal to x and with size equal to K.

      You can see problem 663E - Двоичная табличка and my 17700160 with FFT.
      Also you can look at this HackerRank problem.

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

        Omg, you don't use any single xor operation in your code... I need further elaboration :(

        In FFT after transform you have values in roots of unity. And here?..

        → Reply