Longest Common Extension

Given a string s and some of the pairs (L,R), write a function that will output the length of the longest sub string starting at L and R



s = “abcbabcb”

Queries : (1,3), (1,5), (0,1)


1, for (1,3) starting at index 1 we have ‘b’ and at index 3 also we have ‘b’, but other characters dont match 3 for (1,5) starting at index 1 we have “bcb” and at index 5 we have “bcb” 0 for (0,1) charcters dont match


For each LCE query

1. Initialize length to 0

2. start comparing the characters starting from the indexes L and R

3. If the characters match, then this character is in Longest Common Extension so increament length

4. Else, if the characters mismatch then return the length

C++ Program

using namespace std;

//function to find LCE
int LCE(string str, int n, int L, int R)
    int length = 0;
    //till characters dont match
    while (str[L+length] == str[R+length] &&
            R+length < n)


int main()
    int L = 1;
    int R = 5;
    string str = "abcbabcb";
    int n = str.length();

    cout<<LCE(str, n, L, R);

    return (0);

Try It


Translate ยป