Longest Common Extension / LCE | Set 1 ( Introduction and Naive Method ) | A C ++ Program to find the length of longest common extension using Naive Method ; Structure to represent a query of form ( L , R ) ; A utility function to find longest common extension from index - L and index - R ; A function to answer queries of longest common extension ; Driver Program to test above functions ; LCA Queries to answer
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Query { int L , R ; } ; int LCE ( string str , int n , int L , int R ) { int length = 0 ; while ( str [ L + length ] == str [ R + length ] && R + length < n ) length ++ ; return ( length ) ; } void LCEQueries ( string str , int n , Query q [ ] , int m ) { for ( int i = 0 ; i < m ; i ++ ) { int L = q [ i ] . L ; int R = q [ i ] . R ; printf ( " LCE ▁ ( % d , ▁ % d ) ▁ = ▁ % d STRNEWLINE " , L , R , LCE ( str , n , L , R ) ) ; } return ; } int main ( ) { string str = " abbababba " ; int n = str . length ( ) ; Query q [ ] = { { 1 , 2 } , { 1 , 6 } , { 0 , 5 } } ; int m = sizeof ( q ) / sizeof ( q [ 0 ] ) ; LCEQueries ( str , n , q , m ) ; return ( 0 ) ; }