Submission #395943

#	Time	Username	Problem	Language	Result	Execution time	Memory
395943		ArshiaDadras	원형 문자열 (IZhO13_rowords)	C++14	36 / 100	51 ms	32716 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];

bool smax(int &a, int b) {
	return a < b? a = b, true: false;
}

int calc_lcs(int j) {
	int lcs = 0;
	for (int i = n, st = j - m; i && j > st; )
		if (par[i][j] & 2) {
			i--, j--;
			lcs++;
		}
		else
			par[i][j]? j--: i--;
	return lcs;
}

void build_dp() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= 2 * m; j++) {
			if (s[i - 1] == t[j - 1] && smax(dp[i][j], dp[i - 1][j - 1] + 1))
				par[i][j] = 2;
			if (smax(dp[i][j], dp[i - 1][j]))
				par[i][j] = 0;
			if (smax(dp[i][j], dp[i][j - 1]))
				par[i][j] = 1;
		}
}

int calc_round_lcs() {
	int answer = 0;
	for (int i = 0; i < m; i++)
		answer = max(answer, calc_lcs(m + i));
	return answer;
}

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

void solve() {
	int answer = 0;
	for (int i = 0; i < 2; i++) {
		build_dp();
		reverse(t.begin(), t.end());
		answer = max(answer, calc_round_lcs());
	}
	cout << answer;
}

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

• Subtask 1: 36 / 100