제출 #1118879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118879		hamzabc	원형 문자열 (IZhO13_rowords)	C++14	0 / 100	34 ms	22120 KiB

rowords

#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 == asz || sb == bsz)
		return 0;
	if (memoization[sa + 1][sb + 1] != -1)
		return memoization[sa + 1][sb + 1];
	if (a[sa] == b[sb])
		memoization[sa + 1][sb + 1] = dp(sa + 1, sb + 1) + 1;
	else
		memoization[sa + 1][sb + 1] = max(dp(sa, sb + 1), dp(sa + 1, sb));
	return memoization[sa + 1][sb + 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;
	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; i++){
		memoization[i][0] = 0;
	}
	for (int i = 0; i <= bsz; i++){
		memoization[0][i] = 0;
	}
	for (int i = 0; i < asz; i++){
		for (int o = 0; o < bsz; o++){
			res = max(res, memoization[i][o] + memoization[i + asz + 1][o + bsz + 1] - memoization[i][o + bsz + 1] - memoization[i + asz + 1][o]);
		}
	}
	cout << res;
	return 0;
}

• Subtask 1: 0 / 100