# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1118905 | hamzabc | 원형 문자열 (IZhO13_rowords) | C++14 | 240 ms | 22392 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'
int asz;
int bsz;
string a, b;
vector<vector<int>> memoization;
long long int dp(int sa, int sb){
if (sa == a.size() || sb == b.size())
return 0;
if (memoization[sa][sb] != -1)
return memoization[sa][sb];
dp(sa, sb + 1); dp(sa + 1, sb);
if (a[sa] == b[sb])
memoization[sa][sb] = dp(sa + 1, sb + 1) + 1;
else
memoization[sa][sb] = max(dp(sa, sb + 1), dp(sa + 1, sb));
return memoization[sa][sb];
}
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;
b += b;
memoization.resize(a.size() + 1, vector<int>(b.size() + 1, -1));
dp(0, 0);
int res = 0;
for (int i = 0; i <= asz * 2; i++){
memoization[i][bsz * 2] = 0;
}
for (int i = 0; i <= bsz * 2; i++){
memoization[asz * 2][i] = 0;
}
for (int i = 0; i < asz; i++){
for (int o = 0; o < bsz; o++){
if (a[i + asz] == b[i + bsz] && memoization[i + asz][o + bsz] == memoization[i][o + bsz] && memoization[i + asz][o + bsz] == memoization[i + asz][o]){
res = max(res, memoization[i][o] - memoization[i + asz][o + bsz]);
}
}
}
string aeski = a;
a = "";
for (int i = asz * 2 - 1; i >= 0; i--)
a = a + aeski[i];
for (int i = 0; i < a.size() + 1; i++)
fill(all(memoization[i]), -1);
dp(0, 0);
for (int i = 0; i <= asz * 2; i++){
memoization[i][bsz * 2] = 0;
}
for (int i = 0; i <= bsz * 2; i++){
memoization[asz * 2][i] = 0;
}
for (int i = 0; i < asz; i++){
for (int o = 0; o < bsz; o++){
if (a[i + asz] == b[i + bsz] && memoization[i + asz][o + bsz] == memoization[i][o + bsz] && memoization[i + asz][o + bsz] == memoization[i + asz][o])
res = max(res, memoization[i][o] - memoization[i + asz][o + bsz]);
}
}
cout << res;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |