oj.uz

답안 #100665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100665 2019-03-13T05:54:05 Z ainta 원형 문자열 (IZhO13_rowords) C++17
100 / 100
 126 ms 54380 KB 
#include<cstdio>
#include<algorithm>
using namespace std;
char p[4010], q[2010];
int n, m, D[4010][2010];
int dir[4010][2010], res;
bool OK[4010][2010];
void Do() {
	int i, j;
	for (i = 1; i <= n; i++)p[i + n] = p[i];
	for (i = 0; i <= n + n; i++) {
		for (j = 0; j <= m; j++) {
			dir[i][j] = D[i][j] = 0;
			if (i&&j) {
				if (p[i] == q[j])OK[i][j] = true;
				else OK[i][j] = false;
			}
		}
	}
	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;
			}
		}
	}
	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][y] = 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]);
	}
}
int main() {
	scanf("%s%s", p + 1, q + 1);
	int i;
	for (i = 1; p[i]; i++);
	n = i - 1;
	for (i = 1; q[i]; i++);
	m = i - 1;
	Do();
	reverse(p + 1, p + n + 1);
	Do();
	printf("%d\n", res);
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:75: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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1244 KB Output is correct
6 Correct 26 ms 21880 KB Output is correct
7 Correct 51 ms 35704 KB Output is correct
8 Correct 104 ms 35704 KB Output is correct
9 Correct 97 ms 35704 KB Output is correct
10 Correct 85 ms 35704 KB Output is correct
11 Correct 88 ms 39288 KB Output is correct
12 Correct 82 ms 42972 KB Output is correct
13 Correct 119 ms 42856 KB Output is correct
14 Correct 97 ms 40696 KB Output is correct
15 Correct 105 ms 44024 KB Output is correct
16 Correct 116 ms 38552 KB Output is correct
17 Correct 84 ms 42360 KB Output is correct
18 Correct 112 ms 50680 KB Output is correct
19 Correct 78 ms 35704 KB Output is correct
20 Correct 126 ms 45408 KB Output is correct
21 Correct 53 ms 38264 KB Output is correct
22 Correct 74 ms 43256 KB Output is correct
23 Correct 80 ms 46088 KB Output is correct
24 Correct 84 ms 48668 KB Output is correct
25 Correct 102 ms 54380 KB Output is correct