제출 #100655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
100655		ainta	원형 문자열 (IZhO13_rowords)	C++17	32 / 100	84 ms	54264 KiB

rowords

#include<cstdio>
#include<algorithm>
using namespace std;
char p[4010], q[2010];
int n, m, D[4010][2010];
int dir[4010][2010];
bool OK[4010][2010];
int main() {
	int i, j;
	scanf("%s%s", p + 1, q + 1);
	for (i = 1; p[i]; i++);
	n = i - 1;
	for (i = 1; q[i]; i++);
	m = i - 1;
	for (i = 1; i <= n; i++)p[i + n] = p[i];
	for (i = 1; i <= n+n; i++) {
		for (j = 1; j <= m; j++) {
			if (p[i] == q[j])OK[i][j] = true;
		}
	}
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= m; j++) {
			if (i == 0 && j == 0)continue;
			if (i == 0) continue;
			if (j == 0) {
				dir[i][j] = 2;
				continue;
			}
			D[i][j] = D[i][j - 1];
			if (OK[i][j] && D[i][j] < D[i - 1][j - 1] + 1) {
				D[i][j] = D[i - 1][j - 1] + 1, dir[i][j] = 1;
			}
			if (D[i][j] < D[i - 1][j]) {
				D[i][j] = D[i - 1][j], dir[i][j] = 2;
			}
		}
	}
	int res = 0;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			if (dir[i][j]) {
				break;
			}
		}
		if (j != m + 1) {
			int x = i, y = j;
			dir[x][y] = 0;
			while (x < i + n - 1 && y <= m) {
				if (dir[x + 1][y] == 2) {
					x++;
					dir[x][y] = 0;
				}
				else if (dir[x + 1][y + 1] == 1) {
					x++, y++;
					dir[x + 1][y + 1] = 0;
				}
				else y++;
			}
			if (y <= m) {
				for (j = y; j <= m; j++)D[i+n-1][j]--;
			}
		}
		for (j = 0; j <= m; j++) {
			if (j == 0) {
				dir[i + n][j] = 2;
				D[i + n][j] = D[i + n - 1][j];
				continue;
			}
			D[i+n][j] = D[i+n][j - 1];
			if (OK[i + n][j] && D[i + n][j] < D[i + n - 1][j - 1] + 1)D[i + n][j] = D[i + n - 1][j - 1] + 1, dir[i + n][j] = 1;
			if (D[i + n][j] < D[i + n - 1][j])D[i + n][j] = D[i + n - 1][j], dir[i + n][j] = 2;
		}
		res = max(res, D[i + n][m]);
	}
	printf("%d\n", res);
}

컴파일 시 표준 에러 (stderr) 메시지

rowords.cpp: In function 'int main()':
rowords.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", p + 1, q + 1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 100