Shortest Non Common Subsequence, C++ (gcc)

Shortest Non Common Subsequence

#include <bits/stdc++.h>
using namespace std;
 void SetNext ( const string & s, vector <vector < int >> & nxt) {
     const  int n = s.size ();
     int idx_0 = n + 1 , idx_1 = n + 1 ;
     for ( int i = n; 0 <i ;--i) {
        nxt [i] [ 0 ] = idx_0;
        nxt [i] [ 1 ] = idx_1;
         if (s [i -1 ] == '0' ) idx_0 = i;
         else idx_1 = i;
    }
    nxt [ 0 ] [ 0 ] = idx_0; nxt [ 0 ] [ 1 ] = idx_1;
}
int findMinimum(string p,string q)
{
    const  int n_p = p.size (), n_q = q.size ();
    vector <vector < int >> nxt_p (n_p + 2 , vector < int > ( 2 , n_p + 1 ));
    vector <vector < int >> nxt_q (n_q + 2 , vector < int > ( 2 , n_q + 1 ));
    SetNext (p, nxt_p);
    SetNext (q, nxt_q);

const  int INF = 2 * max (n_p, n_q);
    vector <vector < int >> dp (n_p + 2 , vector < int > (n_q + 2 , INF));
    dp [n_p + 1 ] [n_q + 1 ] = 0 ;
     for ( int i = n_p + 1 ; 0 <= i; --i)
         for ( int j = n_q + 1 ; 0 <= j; --j)
             for ( int k = 0 ; k < 2 ; ++ k)
                 if (dp [nxt_p [i] [k]] [nxt_q [j] [k]] <INF)
                    dp [i] [j] = min (dp [i] [j], dp [nxt_p [i] [k]] [nxt_q [j] [k]] + 1 );

string res;
    for ( int i = 0 , j = 0 ; i <= n_p || j <= n_q;) {
         for ( int k = 0 ; k < 2 ; ++ k) {
             if (dp [i] [j] == dp [nxt_p [i] [k]] [nxt_q [j] [k]] + 1 ) {
                i = nxt_p [i] [k];
                j = nxt_q [j] [k];
                res += ( char ) ( '0' + k);
                 break ;
            }
        }
    }
    return (int)res.size();
}
int main() {
	// your code goes here
string s1,s2;
cin>>s1>>s2;
cout<<findMinimum(s1,s2)<<endl;
	return 0;
}


run \| edit \| history \| help	0