Find the longest sub | C ++ program to find that substring which is its suffix prefix and also found somewhere in between ; Z - algorithm function ; BIT array ; bit update function which updates values from index " idx " to last by value " val " ; Query function in bit ; Driver Code ; Making the z array ; update in the bit array from index z [ i ] by increment of 1 ; if the value in z [ i ] is not equal to ( n - i ) then no need to move further ; queryng for the maximum length substring from bit array
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > z_function ( string s ) { int n = s . size ( ) ; vector < int > z ( n ) ; for ( int i = 1 , l = 0 , r = 0 ; i < n ; i ++ ) { if ( i <= r ) z [ i ] = min ( r - i + 1 , z [ i - l ] ) ; while ( i + z [ i ] < n && s [ z [ i ] ] == s [ i + z [ i ] ] ) z [ i ] ++ ; if ( i + z [ i ] - 1 > r ) l = i , r = i + z [ i ] - 1 ; } return z ; } int n , len = 0 ; int bit [ 1000005 ] ; string s ; vector < int > z ; map < int , int > m ; void update ( int idx , int val ) { if ( idx == 0 ) return ; while ( idx <= n ) { bit [ idx ] += val ; idx += ( idx & - idx ) ; } } int pref ( int idx ) { int ans = 0 ; while ( idx > 0 ) { ans += bit [ idx ] ; idx -= ( idx & - idx ) ; } return ans ; } int main ( ) { s = " geeksisforgeeksinplatformgeeks " ; n = s . size ( ) ; z = z_function ( s ) ; for ( int i = 1 ; i < n ; i ++ ) { update ( z [ i ] , 1 ) ; } for ( int i = n - 1 ; i > 1 ; i -- ) { if ( z [ i ] != ( n - i ) ) continue ; if ( pref ( n ) - pref ( z [ i ] - 1 ) >= 2 ) { len = max ( len , z [ i ] ) ; } } if ( ! len ) cout << " - 1" ; else cout << s . substr ( 0 , len ) ; return 0 ; }