Find minimum shift for longest common prefix | CPP program to find longest common prefix after rotation of second string . ; function for KMP search ; preprocessing of longest proper prefix ; find out the longest prefix and position ; for new position with longer prefix in str2 update pos and len ; print result ; driver function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void KMP ( int m , int n , string str2 , string str1 ) { int pos = 0 , len = 0 ; int p [ m + 1 ] ; int k = 0 ; p [ 1 ] = 0 ; for ( int i = 2 ; i <= n ; i ++ ) { while ( k > 0 && str1 [ k ] != str1 [ i - 1 ] ) k = p [ k ] ; if ( str1 [ k ] == str1 [ i - 1 ] ) ++ k ; p [ i ] = k ; } for ( int j = 0 , i = 0 ; i < m ; i ++ ) { while ( j > 0 && str1 [ j ] != str2 [ i ] ) j = p [ j ] ; if ( str1 [ j ] == str2 [ i ] ) j ++ ; if ( j > len ) { len = j ; pos = i - j + 1 ; } } cout << " Shift ▁ = ▁ " << pos << endl ; cout << " Prefix ▁ = ▁ " << str1 . substr ( 0 , len ) ; } int main ( ) { string str1 = " geeksforgeeks " ; string str2 = " forgeeksgeeks " ; int n = str1 . size ( ) ; str2 = str2 + str2 ; KMP ( 2 * n , n , str2 , str1 ) ; return 0 ; }