# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1125441 | hamzabc | Round words (IZhO13_rowords) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'
vector<vector<long long int>> memoization;
string a, b;
int asz, bsz;
int shft = 0;
long long int dp(int x, int y){
if (x == asz || y == bsz)
return 0;
if (memoization[x][y] != -1){
return memoization[x][y];
}
if (a[x + shft] == b[y])
return dp(x + 1, y + 1) + 1;
return max(dp(x + 1, y), dp(x, y + 1));
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> a >> b;
asz = a.size();
bsz = b.size();
a = a + a;
memoization.resize(asz, vector<long long int>(bsz, -1));
long long int ret = 0;
for (shft = 0; shft < asz; shft++){
for (int i = 0; i < asz; i++)
fill(all(memoization[i]), -1);
ret = max(ret, dp(0, 0));
}
reverse(all(b));
for (shft = 0; shft < asz; shft++){
for (int i = 0; i < asz; i++)
fill(all(memoization[i]), -1);
ret = max(ret, dp(0, 0));
}
cout << ret;
return 0;
}