#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MOD = 1e9 + 7;
const int help = (1 << 11) - 1;
const int MAXN = 1e5;
int n;
vector<int>arr;
vector<int> adj[MAXN + 11];
int offSet = 1e5 + 1;
bool vis[MAXN + 12];
void dfs(int s) {
cout << s << " ";
for (auto child : adj[s]) {
if (vis[child] == 0) {
dfs(child);
}
}
vis[s] = 1;
}
int ans(int i, int j, string &a, string &b, vector<vector<int>>&dp) {
if (i >= a.size() | j >= b.size()) {
return 0;
}
if (dp[i][j] != -1)return dp[i][j];
if (a[i] == b[j]) {
return ans(i + 1, j + 1, a, b, dp) + 1;
}
return dp[i][j] = max(ans(i, j + 1, a, b, dp), ans(i + 1, j, a, b, dp));
}
int LCS(string&a, string&b) {
vector<vector<int>>dp(a.size(), vector<int>(b.size(), -1));
return ans(0, 0, a, b, dp);
}
string left(int i, string &a) {
string ret = "";
// ret.push_back
for (int j = i; j >= 0; j--)ret.push_back(a[j]);
for (int j = a.size() - 1; j > i; j--)ret.push_back(a[j]);
return ret;
}
string right(int i, string& a) {
string ret = "";
// ret.push_back
for (int j = i; j < a.size(); j++)ret.push_back(a[j]);
for (int j = 0; j < i; j++)ret.push_back(a[j]);
return ret;
}
void solve() {
string a, b;
cin >> a >> b;
int ans2 = 0;
string l, r;
for (int rot = 0; rot < a.size(); rot++) {
l = left(rot, a);
r = right(rot, a);
ans2 = max(ans2, max(LCS(l, b), LCS(r, b)));
}
cout << ans2 << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int tt = 1;
//cin>>tt;
while (tt--) {
solve();
}
}
Compilation message
rowords.cpp: In function 'long long int ans(long long int, long long int, std::string&, std::string&, std::vector<std::vector<long long int> >&)':
rowords.cpp:27:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if (i >= a.size() | j >= b.size()) {
| ~~^~~~~~~~~~~
rowords.cpp:27:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if (i >= a.size() | j >= b.size()) {
| ~~^~~~~~~~~~~
rowords.cpp:27:11: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
27 | if (i >= a.size() | j >= b.size()) {
| ~~^~~~~~~~~~~
rowords.cpp: In function 'std::string right(long long int, std::string&)':
rowords.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int j = i; j < a.size(); j++)ret.push_back(a[j]);
| ~~^~~~~~~~~~
rowords.cpp: In function 'void solve()':
rowords.cpp:68:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int rot = 0; rot < a.size(); rot++) {
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2812 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2824 KB |
Output is correct |
| 6 |
Execution timed out |
2096 ms |
3944 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2040 ms |
11100 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2057 ms |
10844 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2023 ms |
11116 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2037 ms |
11032 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2011 ms |
12080 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2062 ms |
13336 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2047 ms |
13320 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2048 ms |
12160 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2045 ms |
14116 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2052 ms |
11764 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2070 ms |
10044 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2072 ms |
13540 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2004 ms |
11384 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2073 ms |
12620 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2013 ms |
5264 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2036 ms |
6928 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2005 ms |
8484 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2023 ms |
8580 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2056 ms |
10532 KB |
Time limit exceeded |
