LCS Returns

QUESTION

Given two strings,a and b, find and print the total number of ways to insert a character at any position in string a such that the length of the Longest Common Subsequence of characters in the two strings increases by one.\n\nInput Format\n\nThe first line contains a single string denoting a. \nThe second line contains a single string denoting b.\n\nConstraints\n\nScoring\n1.1<=|a|,|b|<=5000\n2.Strings a and b are alphanumeric (i.e., consisting of arabic digits and/or upper and lower case English letters).\n3.The new character being inserted must also be alphanumeric (i.e., a digit or upper/lower case English letter).\nSubtask\n1<=|a|,|b|<=1000\n for 66.7% of the maximum score.\nOutput Format\n\nPrint a single integer denoting the total number of ways to insert a character into string a in such a way that the length of the longest common subsequence of a and b increases by one.

ANSWER

#include <bits/stdc++.h>

using namespace std;

int N, M;
char S[5002];
char T[5002];
int dp[5002][5002];
int dp2[5002][5002];
bool ok[256];

int main()
{
    scanf("%s", S+1);
    N=strlen(S+1);
    scanf("%s", T+1);
    M=strlen(T+1);
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
    {
        if(S[i]==T[j])
            dp[i][j]=dp[i-1][j-1]+1;
        else
            dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
    }
    for(int i=N; i>=1; i--) for(int j=M; j>=1; j--)
    {
        if(S[i]==T[j])
            dp2[i][j]=dp2[i+1][j+1]+1;
        else
            dp2[i][j]=max(dp2[i+1][j], dp2[i][j+1]);
    }
    int lcs=dp[N][M];
    int ans=0;
    for(int i=0; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            if(dp[i][j-1]+dp2[i+1][j+1]==lcs)
                ok[(int)T[j]]=true;
        }
        for(int j=0; j<256; j++)
        {
            ans+=ok[j];
            ok[j]=false;
        }
    }
    printf("%d\n", ans);
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro