Find the longest sub | C ++ implementation of the approach ; Function to find longest prefix suffix ; To store longest prefix suffix ; Length of the previous longest prefix suffix ; lps [ 0 ] is always 0 ; Loop calculates lps [ i ] for i = 1 to n - 1 ; ( pat [ i ] != pat [ len ] ) ; If len = 0 ; Function to find the longest substring which is prefix as well as a sub - string of s [ 1. . . n - 2 ] ; Find longest prefix suffix ; If lps of n - 1 is zero ; At any position lps [ i ] equals to lps [ n - 1 ] ; If answer is not possible ; Driver code ; function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > compute_lps ( string s ) { int n = s . size ( ) ; vector < int > lps ( n ) ; int len = 0 ; lps [ 0 ] = 0 ; int i = 1 ; while ( i < n ) { if ( s [ i ] == s [ len ] ) { len ++ ; lps [ i ] = len ; i ++ ; } else { if ( len != 0 ) len = lps [ len - 1 ] ; else { lps [ i ] = 0 ; i ++ ; } } } return lps ; } void Longestsubstring ( string s ) { vector < int > lps = compute_lps ( s ) ; int n = s . size ( ) ; if ( lps [ n - 1 ] == 0 ) { cout << -1 ; return ; } for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( lps [ i ] == lps [ n - 1 ] ) { cout << s . substr ( 0 , lps [ i ] ) ; return ; } } if ( lps [ lps [ n - 1 ] - 1 ] == 0 ) cout << -1 ; else cout << s . substr ( 0 , lps [ lps [ n - 1 ] - 1 ] ) ; } int main ( ) { string s = " fixprefixsuffix " ; Longestsubstring ( s ) ; return 0 ; }