Length of longest substring to be deleted to make a string equal to another string | C ++ Program to implement the above approach ; Function to print the length of longest substring to be deleted ; Stores the length of string ; Store the position of previous matched character of str1 ; Store the position of first occurrence of str2 in str1 ; Find the position of the first occurrence of str2 ; Store the index of str1 ; If both characters not matched ; Store the length of the longest deleted substring ; Store the position of last occurrence of str2 in str1 ; If both characters not matched ; Update res ; Update res . ; Driver Code ; Given string ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longDelSub ( string str1 , string str2 ) { int N = str1 . size ( ) ; int M = str2 . size ( ) ; int prev_pos = 0 ; int pos [ M ] ; for ( int i = 0 ; i < M ; i ++ ) { int index = prev_pos ; while ( index < N && str1 [ index ] != str2 [ i ] ) { index ++ ; } pos [ i ] = index ; prev_pos = index + 1 ; } int res = N - prev_pos ; prev_pos = N - 1 ; for ( int i = M - 1 ; i >= 0 ; i -- ) { int index = prev_pos ; while ( index >= 0 && str1 [ index ] != str2 [ i ] ) { index -- ; } if ( i != 0 ) { res = max ( res , index - pos [ i - 1 ] - 1 ) ; } prev_pos = index - 1 ; } res = max ( res , prev_pos + 1 ) ; return res ; } int main ( ) { string str1 = " GeeksforGeeks " ; string str2 = " forks " ; cout << longDelSub ( str1 , str2 ) ; return 0 ; }