Understanding the algorithm for pattern matching using an LCP array

This answer takes reference from the following:

• Manber, Myers '93
• MIT's Suffix Array notes from 2007
• @jogojapan's answer
• Luke Videckis' implementation, which most of my code is based on

Recently I had been researching on string pattern matching and came across the described technique from various sources, but I hadn't seen a proper implementation of it.

Initially I coded something but it was wrong and I couldn't wrap my head around it. It wasn't until Luke shared his implementation that I finally understood what went wrong. Given the lack of actual code on this, I thought I would just add it here for future reference.

I shall first redefine some variables from OP's snippet. The original was fairly confusing for me.

l (lowercase) - running counter for matched characters from the left of the suffix array
r (lowercase) - running counter for matched characters from the right of the suffix array
L (uppercase) - binary search left bound
R (uppercase) - binary search right bound

Instead of using the LCP-LR array that is described in @jogojapan's answer, we look at MIT's Suffix Array notes from 2007. There, the lcp function is defined to be

lcp(l, r) = min(LCP[l], LCP[l + 1], ..., LCP[r - 1])

With some precomputation of the LCP array, you can build a Sparse Table in O(n) time to answer range minimum queries in O(1) time. Then, we have the following code:

pair<int, int> search(string &t, SparseTable<int> &lcp_st) {
    int match_l = mismatch(t.begin(), t.end(), s.begin() + SA.front(), s.end()).first - t.begin(),
        match_r = mismatch(t.begin(), t.end(), s.begin() + SA.back(), s.end()).first - t.begin(),
        match_m, l = 0, r = s.size(), m;

    auto update_match = [&]() {
        if (SA[m] + match_m < s.size() && s[SA[m] + match_m] > t[match_m]) {
            r = m;
            match_r = match_m;
        } else {
            l = m;
            match_l = match_m;
        }
    };

    auto match_lcp = [&](int m) -> pair<int, int> {
        auto search_half = [&](bool left) {
            int l = left ? -1 : m, r = left ? m : s.size();
            while (l + 1 < r) {
                int mid = l + (r - l) / 2;

                if (lcp_st.range_query(left ? mid : l, left ? r - 1 : mid - 1) < t.size()) (left ? l : r) = mid;
                else (left ? r : l) = mid;
            }
            return r;
        };

        return {search_half(true), search_half(false)};
    };

    while (l + 1 < r) {
        m = l + (r - l) / 2;

        if (match_l < match_r) {
            int lcp = lcp_st.range_query(m, r - 1);

            if (match_r < lcp) r = m;
            else if (match_r > lcp) l = m;
            else {
                match_m = mismatch(t.begin() + match_r, t.end(), s.begin() + SA[m] + match_r, s.end()).first - t.begin();

                if (match_m != t.size()) update_match();
                else return match_lcp(m);
            }
        } else {
            int lcp = lcp_st.range_query(l, m - 1);

            if (match_l < lcp) l = m;
            else if (match_l > lcp) r = m;
            else {
                match_m = mismatch(t.begin() + match_l, t.end(), s.begin() + SA[m] + match_l, s.end()).first - t.begin();

                if (match_m != t.size()) update_match();
                else return match_lcp(m);
            }
        }
    }

    return {l, r}; //dummy pair if no occurrences
}

where the following variables are defined as

s - text
t - pattern
SA - suffix array
lcp_st - minimum sparse table built from LCP array of the suffix array
lcp_st.range_query(l, r - 1) - returns lcp(l, r)
match_l - l (lowercase) as defined above
match_r - r (lowercase) as defined above
match_m - updated match with SA[m], continuing from the last matched character
l - binary search left bound as defined above
r - binary search right bound as defined above
m - binary search middle
update_match() - if the pattern hasn't been fully found, update search
match_lcp(m) - pattern has been found at SA[m], find SA index range of occurrences [l, r)

respectively in my code snippet.