# 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);
}```

Translate »