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

Example

INPUT

s = “abcbabcb”

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

OUTPUT

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

Algorithm

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

#include<bits/stdc++.h>
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)
        length++;

    return(length);
}


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


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

    return (0);
}