Code:
int fun(string T, string S){
int m = T.size();
int n = S.size();
if(m>n) return 0;
int dp[m+1][n+1];
for (int i = 1; i <= n; i++)
dp[0][i] = 1;
for (int j = 0; j <= m; j++)
dp[j][0] = 0;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(T[i-1]!=S[j-1]){
dp[i][j] = dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
}
}
}
return dp[m][n];
}
It should be :
if(T[i-1]!=S[j-1]){
dp[i][j] = dp[i][j-1];
}
else{
dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
}
PS:According to function parameters ‘A’ and ‘B’, take string ‘T’ as ‘B’ and string ‘S’ as ‘A’ .
Be clear T is “bigger” string and S is “smaller” string.Here “smaller” means its occurrences have to be found.
Problem 1: remove statement if(m>n) return 0; because firstly its incorrect and secondly if it was correct and performed what you intended it to do then also it is not needed and redundant.
Problem 2: in first for loop it should be dp[0][i]=0; as there is no sub sequence occurrence in an empty string.
Problem 3: in second for loop it should be dp[j][0]=1; as null string is a sub-sequence to any parent string.
This should work i checked it.