import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;
public class main {
public static int solution(String s1 , String s2 , int si ,int ti , int[][] dp){
//base case if target ends
if(ti == s2.length())
return 1;
//if source string ends
else if(si == s1.length())
return 0;
//memoization , if answer is already calculated return it
if(dp[si][ti] != -1)
return dp[si][ti];
//taking out characters
char ch1 = s1.charAt(si) , ch2 = s2.charAt(ti);
int totalways = 0;
//if chars are not equal we delete source character and give a call
if(ch1 != ch2)
totalways = solution(s1 , s2 , si+1 , ti , dp);
//if chars are equal we give 2 calls 1 with both matching other with removing
//only source character
else{
int tw1 = solution(s1,s2,si+1,ti+1,dp);
int tw2 = solution(s1,s2,si+1,ti,dp);
totalways = tw1 + tw2;
}
dp[si][ti] = totalways;
return totalways;
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
String s1 = scn.next();
String s2 = scn.next();
int[][] dp = new int[s1.length()][s2.length()];
for(int i = 0 ; i < dp.length ; i++){
for(int j = 0 ; j < dp[0].length ; j++)
dp[i][j] = -1;
}
System.out.println(solution(s1, s2 , 0 ,0 , dp));
}
}
Comments