массивы — ошибки реализации самой длинной общей подпоследовательности C ++ O (n * m)

Я прохожу некоторые статьи по динамическому программированию на geeksforgeeks и перебираю Самая длинная общая подпоследовательность проблема. Я не придумал реализацию экспоненциального наивного решения самостоятельно, однако, разработав несколько примеров проблемы на бумаге, я придумал, что я считаю успешной реализацией O(n*m) версия Однако OJ доказал, что я неправ. Мой алгоритм не работает с входными строками:

• "LRBBMQBHCDARZOWKKYHIDDQSCDXRJMOWFRXSJYBLDBEFSARCBYNECDYGGXXPKLORELLNMPAPQFWKHOPKMCO"
• "QHNWNKUEWHSQMGBBUQCLJJIVSWMDKQTBXIXMVTRRBLJPTNSNFWZQFJMAFADRRWSOFSBCNUVQHFFBSAQXWPQCAC"

Мой мыслительный процесс для алгоритма заключается в следующем. Я хочу сохранить массив DP, длина которого равна длине строки a где a является меньшей из входных строк. dpA[i] будет самой длинной общей подпоследовательностью, заканчивающейся на a[i], Для этого мне нужно перебрать строку a из индекса 0 => length-1 и посмотреть, если a[i] существует в b, Если a[i] существует в b это будет в положении pos,

1. Первая оценка dp[i] как 1 если dp[i] было 0
2. Знать что a[i] это расширение существующей подпоследовательности, которую мы должны пройти a и найти первого персонажа позади i это соответствует значению в b позади pos, Давайте назовем индексы этих совпадающих значений j а также k соответственно. Это значение гарантированно будет значением, которое мы видели раньше, так как мы охватили все a[0...i-1] и заполнили dpA[0...i-1], Когда мы найдем первый матч, dpA[i] = dpA[j]+1 потому что мы расширяем предыдущую подпоследовательность, которая заканчивается a[j], Промыть, повторить.

Очевидно, что этот метод не идеален, иначе я бы не задавал этот вопрос, но я не могу понять проблему с алгоритмом. Я смотрю на это так долго, что вряд ли могу думать об этом больше, но любые идеи о том, как это исправить, будут с благодарностью!

int longestCommonSubsequenceString(const string& x, const string& y) {
string a = (x.length() < y.length()) ? x : y;
string b = (x.length() >= y.length()) ? x : y;

vector<int> dpA(a.length(), 0);

int pos;
bool breakFlag = false;

for (int i = 0; i < a.length(); ++i) {

pos = b.find_last_of(a[i]);

if (pos != string::npos) {

if (!dpA[i]) dpA[i] = 1;

for (int j = i-1; j >= 0; --j) {
for (int k = pos-1; k >= 0; --k) {
if (a[j] == b[k]) {
dpA[i] = dpA[j]+1;
breakFlag = true;
break;
}
if (breakFlag) break;
}
}
}

breakFlag = false;
}

return *max_element(dpA.begin(), dpA.end());
}

РЕДАКТИРОВАТЬ

Я думаю, что сложность может быть на самом деле O(n*n*m)