제출 #1118871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118871		hamzabc	원형 문자열 (IZhO13_rowords)	C++14	24 / 100	23 ms	5968 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][sb] != -1)
		return memoization[sa][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();
	vector<int> lastseen('z' - 'a' + 1, -1);
	memoization.resize(a.size(), vector<int>(b.size(), -1));
	for (int i = 0; i < asz; i++){
		if (lastseen[a[i] - 'a'] == -1)
			lastseen[a[i] - 'a'] = i;
	}
	for (int i = 0; i < bsz; i++){
		if (lastseen[b[i] - 'a'] != -1){
			string aeski = a;
			a = "";
			for (int o = 0; o < asz; o++)
				a += aeski[(lastseen[b[i] - 'a'] + o) % asz];
			string beski = b;
			b = "";
			for (int o = 0; o < bsz; o++)
				b += beski[(i + o) % bsz];
			cout << dp(0, 0);
			return 0;
		}
	}
	cout << "0";
	return 0;
}

• Subtask 1: 24 / 100