Наивный подход к самой длинной общей подпоследовательности

Мы изучали теорию динамического программирования в течение осеннего квартала, и я пытаюсь освежить ее и продолжить ее изучение. В настоящее время я пытаюсь наивный подход к проблеме LCS, как упомянуто в этой статье TopCoder: Динамическое программирование

Алгоритм выглядит следующим образом:

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)

Например, учитывая строки «ABCDE» и «DACACBE», самая длинная общая подпоследовательность — «ACE».

Тем не менее, мой выводит правильную подстроку «ABE» вместо правильной «ACE». Что не так с порядком моей реализации?

#include <iostream>
#include <string>
using namespace std;string LCS(string s, string t);

int main(){
string A = "ABCDE";
string B = "DACACBE";
cout << LCS(A,B) << 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() > b.length()){
return a;
}
else{
return b;
}
}
}