제출 #1119459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119459		Tsagana	원형 문자열 (IZhO13_rowords)	C++14	100 / 100	63 ms	63172 KiB

rowords

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();

using namespace std;

string s, t;
int n, m, k;
int R[2001][4001];
int L[2001][4001];

int calc() {
	int ans = 0;

	memset(R, 0, sizeof R);
	memset(L, 0, sizeof L);

	for (int i = 1; i <= m; i++) R[0][i] = i;

	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++) {
		if (s[i] == t[j]) {
			R[i][j] = L[i][j-1];
			L[i][j] = R[i-1][j];
		}
		else {
			R[i][j] = max(L[i][j-1], R[i-1][j]);
			L[i][j] = min(L[i][j-1], R[i-1][j]);
		}
	}
	
	for (int i = 1; i <= k; i++) {
		int cnt = 0;
		for (int j = i; j <= i+k-1; j++) if (R[n][j] <= i-1) cnt++;
		ans = max(ans, cnt);
	}
	return ans;
}
void solve () {
	cin >> s >> t;

	n = s.size();
	k = t.size();
	m = 2 * k;
	s = " " + s;
	t = " " + t + t;

	int ans = calc();
	reverse(t.begin()+1, t.begin()+m+1);
	ans = max(ans, calc());

	cout << ans;
}
int main() {IOS solve(); return 0;}

• Subtask 1: 100 / 100