Same problem https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

What are the constraints of the problem?

If you're okay with an n*m solution (where n is the length of A and m is the length of B) then you can have a dp where dp[pos][matched] is a state where you're at some character in A and you've matched "matched" characters of B so far. So when processing a character of A (we'll call it c), there are two situations:

c is equal to the next character in B (B[matched]) and we go to state dp[pos+1][matched+1] or it doesn't match the next character and we go to state dp[pos+1][biggestMatchedPrefix] (see despotovski01's comment) and add 1 to the returned value (since we're increasing the subsequence size by 1). And of course if "matched" is ever equal to the length of B, then this is invalid since we've matched all of B (thus it's a substring of this subsequence)

Or we choose to not take that character and go to state dp[pos+1][matched] and add 0 because we aren't increasing the subsequence size.

If you're looking for a faster solution, I can't really think of one at the moment.

This problem can be solved in O(|A| * |B|) complexity. The main idea of the solution includes dynamic programming.

We have two parameters in our dp states. First one is obviously the position of string A we are currently at, the second one is the length of prefix of string B which has been matched with the current subsequence. Let's denote these parameters as X and Y respectively.

Now, at position X we can either include this in our subsequence or skip it. If we skip it, our next call will be dp(X + 1, Y).

Now come to the inclusion part. There are two cases.

First Case: If our character at position X of string A matches with the character at position Y of string B, then our call will be 1 + dp(X + 1, Y + 1). Basically we increment each parameters by one as it matched.

Second Case: If our character at those positions do not match, we can not simply call dp(X + 1, 0). Because there is a possibility that some suffix of our subsequence matches with the prefix of string B. Check this part in following code and try to understand.

The F array gives us the length of the prefix which is also a suffix at that position. KMP was used to do this in O(N).

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;
int F[N];
string A,B;

void kmp()
{
   F[0] = 0;
   for(int i = 1;i<B.size();i++){
      int j = F[i-1];
      while(j > 0 and B[j] != B[i]){
         j = F[j-1];
      }
      if(B[i] == B[j])j++;
      F[i] = j;
   }
}

int dp[N][N];

int call(int x,int y)
{
    if(y == B.size())return -1e5;
    if(x == A.size())return 0;
    if(dp[x][y] != -1)return dp[x][y];

    int ret = call(x + 1,y);

    if(A[x] == B[y]){
        ret = max(ret,1 + call(x + 1,y + 1));
    }else{
        if(y > 0)ret = max(ret,call(x,F[y - 1]));
        else ret = max(ret,1 + call(x + 1,0));
    }
    return dp[x][y] = ret;
}
int main()
{
    cin >> A >> B;
    kmp();
//    for(int i = 0;i < B.size();i++)cout << F[i] << " ";cout << endl;
    memset(dp,-1,sizeof dp);
    cout << call(0,0) << "\n";
}