Longest Common Subsequence using bit operations?

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

class Solution {
public:
    int longestCommonSubsequence(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;
        int w = (m + 31) >> 5;
        std::uint32_t S[256][w];
        std::memset(S, 0, sizeof(std::uint32_t) * 256 * w);
        std::int32_t set = 1;
        for (int i = 0, j = 0; i < m; ++i) {
            S[X[i]][j] |= set;
            set <<= 1;
            if (!set) set++,j++;
        }
        std::uint32_t L[w];
        std::memset(L, 0, sizeof(std::uint32_t) * w);
        for (int i = 0; i < n; ++i) {
            std::uint32_t b1 = 1;
            std::uint32_t b2 = 0;
            for (int j = 0; j < w; ++j) {
                std::uint32_t U  = L[j] | S[Y[i]][j];
                std::uint32_t c  = L[j] >> 31;
                std::uint32_t V  = U - (L[j] << 1 | b1+b2);
                b1 = c;
                b2 = (V > U);
                L[j] = U & (~V);
            }
        }      
        int res = 0;
        for (int i = 0; i < w; ++i)
            for (; L[i]; ++res)
                L[i] &= L[i] - 1;
        return res;
    }
};

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 modified the code a bit and got it to run in 3 ms, but i still could not understand it.

My optimized code

#include <cstring>

typedef unsigned int uint;

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;
        int w = (m + 31) >> 5;
        uint S[256][w];
        memset(S, 0, sizeof(S));
        uint set = 1;
        for (int i = 0, j = 0; i < m; ++i) {
            S[X[i]][j] |= set;
            set <<= 1;
            if (!set) set++,j++;
        }
        uint L[w];
        memset(L, 0, sizeof(L));
        for (int i = 0; i < n; ++i) {
            uint b1 = 1;
            uint b2 = 0;
            for (int j = 0; j < w; ++j) {
                uint U  = L[j] | S[Y[i]][j];
                uint V  = U - (L[j] << 1 | b1+b2);
                b1 = L[j] >> 31;
                b2 = (V > U);
                L[j] = U & (~V);
            }
        }      
        int res = 0;
        for (int i = 0; i < w; ++i)
            res += __builtin_popcount(L[i]);
        return res;
    }

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

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

Rev.	By	When	Δ	Comment
en3	ClosetNarcissist	2024-03-24 17:40:03	13
en2	ClosetNarcissist	2024-03-23 22:07:27	22	Tiny change: 'ommon Substring](https://' -> 'ommon Subsequence](https://'
en1	ClosetNarcissist	2024-03-23 21:48:14	3190	Initial revision (published)

Rev.

Lang.

When

Comment

en3

ClosetNarcissist

2024-03-24 17:40:03

en2

ClosetNarcissist

2024-03-23 22:07:27

Tiny change: 'ommon Substring](https://' -> 'ommon Subsequence](https://'

en1

ClosetNarcissist

2024-03-23 21:48:14

3190

Initial revision (published)

History