제출 #395927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
395927		ArshiaDadras	원형 문자열 (IZhO13_rowords)	C++14	20 / 100	30 ms	32736 KiB

rowords

/* In the name of Allah */
// Those were the days, my friend...
#include<bits/stdc++.h>
using namespace std;

string s, t;
const int N = 2e3 + 5;
int n, m, dp[N][2 * N], par[N][2 * N];

int calc(int i, int j, int st) {
	int lcs = 0;
	while (i && j > st)
		if (par[i][j])
			par[i][j] & 1? j--: i--;
		else {
			i--, j--;
			lcs++;
		}
	return lcs;
}

void read_input() {
	cin >> s >> t;
	n = s.size();
	m = t.size();
}

void solve() {
	t += t;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 2 * m; j++)
			if (s[i - 1] == t[j - 1])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else {
				dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
				par[i][j] = dp[i][j] > dp[i][j - 1]? 2: 1;
			}
}

void write_output() {
	int answer = 0;
	for (int i = 0; i < m; i++)
		answer = max(answer, calc(n, m + i, i));
	cout << answer;
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve(), write_output();
	return 0;
}

• Subtask 1: 20 / 100