| 4 | #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); |
| 5 | |
| 6 | int main() |
| 7 | { |
| 8 | // for faster input and output |
| 9 | fastio |
| 10 | string s1,s2; |
| 11 | // inputing the strings |
| 12 | cin>>s1; |
| 13 | cin>>s2; |
| 14 | int n = s1.size(); |
| 15 | int m = s2.size(); |
| 16 | /* Initialization of DP array. Here dp[i][j] is the length of the comman substring that |
| 17 | can be made considering substring s1(..i) and s2(..j) where s(..i) is the substring |
| 18 | considering string from starting to index i. |
| 19 | Thus we have our recurrence relation based on two cases- |
| 20 | 1) if s1[i] == s2[j] (here we take the comman character and increment the comman string by 1) |
| 21 | 2) id s1[i]!= s2[j], then we take the maximum if we take we skip i-th character of s1, or |
| 22 | j-th character of s2 thus having the recurrences as follows. |
| 23 | dp[i][j] = 1+dp[i-1][j-1] given s1[i] == s2 [j] |
| 24 | dp[i][j] = max(dp[i-1][j], dp[i][j-1]) given s1[i] != s2[j] |
| 25 | */ |
| 26 | int** dp = new int* [n+1]; |
| 27 | for(int i=0;i<=n;i++) |
| 28 | { |
| 29 | dp[i] = new int[m+1](); |
| 30 | } |
| 31 | for(int i=0;i<n;i++) |
| 32 | { |
| 33 | for(int j=0;j<m;j++) |
| 34 | { |
| 35 | // Case-1 |
| 36 | if(s1[i] == s2[j]) |
| 37 | { |
| 38 | dp[i+1][j+1] = 1 + dp[i][j]; |
| 39 | } |
| 40 | //Case-2 |
| 41 | else{ |
| 42 | dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]); |
| 43 | } |
| 44 | } |
| 45 | } |
| 46 | // at the end the result is stored in dp[n][m] (considering whole strings as per our dp logic) |
| 47 | cout<< dp[n][m] << endl; |
| 48 | return 0; |
| 49 | } |