Harolinch's blog

By Harolinch, 5 weeks ago, In English,

I need your help given string A, B. How to find longest subsequence of A that doesn't include B as substring ?

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no not the same, please spend some time understanding before answering ...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the constraints of the problem?

»
5 weeks ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    You've made a little mistake, when c doesn't match the next character, we don't necessarily go to 0 matched characters, but to the longest prefix of B that is also the suffix of B[matched] + c. Think like the KMP failure function.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Right I thought I was forgetting something. I think this is actually just very similar to this problem. Thanks for the correction!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        this problem statement want to find LCS between A and B that doesn't include C as substring.

        i want to make sure .. is it the same as to find D = LCS between A and B. and then find longest subsequence of D that doesn't include C

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          That's actually not the case. Consider this test case:

          A = viviviaba

          B = abavivivi

          C = vi

          D = vivivi

          But the longest subsequence of D that doesn't contain C is 2 ("iv"). But if you instead took the subequence "aba" from A and B, you could get an answer of 3.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            now the idea is very clear, thanks a lot Ahmad :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot :)

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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";
}