Longest repeating and non | C ++ program to find the longest repeated non - overlapping substring ; Returns the longest repeating non - overlapping substring in str ; building table in bottom - up manner ; ( j - i ) > LCSRe [ i - 1 ] [ j - 1 ] to remove overlapping ; updating maximum length of the substring and updating the finishing index of the suffix ; If we have non - empty result , then insert all characters from first character to last character of string ; Driver program to test the above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; string longestRepeatedSubstring ( string str ) { int n = str . length ( ) ; int LCSRe [ n + 1 ] [ n + 1 ] ; memset ( LCSRe , 0 , sizeof ( LCSRe ) ) ; int i , index = 0 ; for ( i = 1 ; i <= n ; i ++ ) { for ( int j = i + 1 ; j <= n ; j ++ ) { if ( str [ i - 1 ] == str [ j - 1 ] && LCSRe [ i - 1 ] [ j - 1 ] < ( j - i ) ) { LCSRe [ i ] [ j ] = LCSRe [ i - 1 ] [ j - 1 ] + 1 ; if ( LCSRe [ i ] [ j ] > res_length ) { res_length = LCSRe [ i ] [ j ] ; index = max ( i , index ) ; } } else LCSRe [ i ] [ j ] = 0 ; } } if ( res_length > 0 ) for ( i = index - res_length + 1 ; i <= index ; i ++ ) res . push_back ( str [ i - 1 ] ) ; return res ; } int main ( ) { string str = " geeksforgeeks " ; cout << longestRepeatedSubstring ( str ) ; return 0 ; }