Chef Starts Coding- Editorial || CHEFCODER

editorial
, , ,
1

PROBLEM LINK: Chef Starts Coding | CodeChef

Problem Code: Chef Starts Coding | CodeChef

Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef

Contest : Code to Compete Coding Competition | CodeChef

Author: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

DIFFICULTY:

Easy-Med

PROBLEM:

Chef has started coding recently. He has 2 files with a string name each with length N and M. The two files have code in them in the same sequence of the name of the file given (imagine the file name is AWD that means the function A is written first then function W is written and then function D is written) . Chef wants to find the number of maximum common function sequences present in both of the file names so that he can continue doing his work.

EXPLANATION:
Save data while traversing.

SOLUTION:
C++:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100001;
int t;
int n, q, k, m;
vector primes(N);

void solve() {
string a, b;
cin >> a >> b;
n = (int) a.size();
m = (int) b.size();

vector<vector<int>> dp(n, vector<int>(m));

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int& cur = dp[i][j];
if (a[i] == b[j]) {
cur = 1;
if (i && j) {
cur += dp[i - 1][j - 1];
}
}
else {
if (j) {
cur = dp[i][j - 1];
}
if (i && cur < dp[i - 1][j]) {
cur = dp[i - 1][j];
}
}
}
}
cout << dp[n - 1][m - 1] << “\n”;
}

int main() {
cin >> t;
while (t–) {
solve();
}
return 0;
}