title: Naive Approach to Longest Common Subsequence
body: <p>We studied dynamic programming theory over Fall quarter, and I'm trying to brush up and continue further studies into it. I'm currently trying a naive approach into the LCS problem as mentioned in this TopCoder article: <a href="https://community.topcoder.com/tc?module=Static&amp;d1=features&amp;d2=040104" rel="nofollow">Dynamic Programming </a></p>
  
  <p>The algorithm is as follows:</p>
  
  <pre><code>function LCS(S, T)
     if S is empty or T is empty then
        return empty string
  
     if first char of S == first char of T then
         return (first char of S) + LCS(S - first char, T - first char)
  
     otherwise // first chars are different
         return longer of LCS(S - first char, T) and LCS(S, T - first char)
  </code></pre>
  
  <p>For example, given the strings "ABCDE" and "DACACBE", the longest common subsequence is "ACE".</p>
  
  <p>However, my outputs the valid substring "ABE" instead of correct "ACE". What's wrong with the ordering of my implementation?</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string&gt;
  using namespace std;
  
  
  string LCS(string s, string t);
  
  int main(){
    string A = "ABCDE";
    string B = "DACACBE";
    cout &lt;&lt; LCS(A,B) &lt;&lt; endl;
    return 0;
  }
  
  string LCS(string s, string t){
  
    string sSub = "";
    string tSub = "";
    if(!s.empty())
      sSub = s.substr(1);
    if(!t.empty())
      tSub = t.substr(1);
  
    if(s.empty() || t.empty()){
      return ""; // return an empty string if either are empty
    }
  
    if(s[0] == t[0]){
      string firstOfS = "";
      firstOfS += s[0];
      firstOfS += LCS(sSub, tSub);
      return s[0] + LCS(sSub, tSub);
    }
  
    else{
      string a = LCS(sSub, t);
      string b = LCS(s, tSub);
      if(a.length() &gt; b.length()){
        return a;
      }
      else{
        return b;
      }
    }
  }
  </code></pre>