ClosetNarcissist's blog

Longest Common Subsequence using bit operations?
By ClosetNarcissist, history, 7 months ago, In English

Recently i did Leetcode Longest Common Subsequence problem. I used the basic dp approach and solved it in 18 ms using 12 mb space. After that i decided to check the fastest solutions for the problem and got this code

Fastest LCS code

I submitted it and it ran in 4 ms using 7.5 mb space. I tried to deconstruct the algorithm and understand how it was working. I cleaned the code a bit and got it to run in 3 ms, but I still could not understand it.

My optimized code

I could not find any relevant blogs explaining it. Can anyone help me understand how this works or link any blogs. Thanks.

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

»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ClosetNarcissist (previous revision, new revision, compare).

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

I have simplified the code as much as i can and this is what i got

const int MAX = 1010;

bitset<MAX> operator+(bitset<MAX> a, bitset<MAX> b){
    bitset<MAX> t;
    while(!b.none())
        t=a, a^=b, (b&=t)<<=1;
    return a;
}
bitset<MAX> operator-(bitset<MAX> a, bitset<MAX> b){
    b.flip();
    int i;
    for(i = 0; b[i]; ++i)
        b[i]=0;
    b[i]=1;
    return a+b;
}

class Solution {
public:
    int lcs(string X, string Y){
        if ( X.size() < Y.size() ) swap(X,Y) ;
        int m = X.size() , n = Y.size();
        if (m == 0 || n == 0) return 0;
        bitset<MAX> S[256];
        for (int i = 0, j = 0; i < m; ++i)
            S[X[i]][i] = true;
        bitset<MAX> L;
        for (int i = 0; i < n; ++i) {
            bitset<MAX> U = L | S[Y[i]];
            bitset<MAX> V = U - (L<<1).set(0);
            L = U & (~V);
        }
        return L.count();
    }

    int longestCommonSubsequence(string text1, string text2) {
        return lcs(text1, text2);
    }
};

It is slower now, getting AC at 106ms, using 9.4mb (way worse than even the basic solution to LCS) but it does a fine job of representing what the code in question is actually doing.

Deconstructing the code did give me a greater insight into it but I still don't have a complete idea of how it works.

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

    One thing to note is that the last loop where the bitset L is getting modified, contains the Longest Common Subsequence between string Y and the substring of X from [0, i] after each iteration. So, you could make an vector array of size n and store the L.count() after every iteration to return it and use it in main.

    P.S. If you have a better implementation of bigint then you can easily make this algorithm faster. My bitset implementation of bigint, while providing me with clarity, was obviously more slower than the bigint implementation in the original code (Thus resulting in more time taken).

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

ClosetNarcissist see here: A Bit-String Longest-Common-Subsequence Algorithm

→ Reply