Shortest Uncommon Subsequence | A simple recursive C ++ program to find shortest uncommon subsequence . ; A recursive function to find the length of shortest uncommon subsequence ; S string is empty ; T string is empty ; Loop to search for current character ; char not found in T ; Return minimum of following two Not including current char in answer Including current char ; Driver program to test the above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1005 NEW_LINE int shortestSeq ( char * S , char * T , int m , int n ) { if ( m == 0 ) return MAX ; if ( n <= 0 ) return 1 ; int k ; for ( k = 0 ; k < n ; k ++ ) if ( T [ k ] == S [ 0 ] ) break ; if ( k == n ) return 1 ; return min ( shortestSeq ( S + 1 , T , m - 1 , n ) , 1 + shortestSeq ( S + 1 , T + k + 1 , m - 1 , n - k - 1 ) ) ; } int main ( ) { char S [ ] = " babab " ; char T [ ] = " babba " ; int m = strlen ( S ) , n = strlen ( T ) ; int ans = shortestSeq ( S , T , m , n ) ; if ( ans >= MAX ) ans = -1 ; cout << " Length ▁ of ▁ shortest ▁ subsequence ▁ is : ▁ " << ans << endl ; return 0 ; }