oj.uz

답안 #124945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
124945 2019-07-04T07:46:52 Z 김세빈(#3048) Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 274 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

char S1[3030], S2[3030];
int M[3030], A[3030], B[3030];
int n, m, x, a, b;

void f(int t, int &x, int &a, int &b)
{
	int i, j;
	
	for(i=0; i<n; i++){
		A[i] = B[i] = 0;
	}
	
	for(i=0; i<m; i++){
		M[i] = 0;
	}
	
	for(i=t+1, j=t; i<m; ){
		if(S2[i] == S2[j]) M[i++] = ++j;
		else if(j > t) j = M[j - 1];
		else j = t, i ++;
	}
	
	for(i=0, j=t; i<n; ){
		if(j < m && S1[i] == S2[j]) A[i++] = ++j - t;
		else if(j > t) j = M[j - 1];
		else j = t, i ++;
	}
	
	reverse(S2, S2 + t);
	
	for(i=1, j=0; i<t; ){
		if(S2[i] == S2[j]) M[i++] = ++j;
		else if(j) j = M[j - 1];
		else j = 0, i ++;
	}
	
	for(i=n-1, j=0; i>=0; ){
		if(j < t && S1[i] == S2[j]) B[i--] = ++j;
		else if(j) j = M[j - 1];
		else j = 0, i --;
	}
	
	reverse(S2, S2 + t);
	
	for(i=0; i<=n; i++){
		if((i? A[i - 1] : 0) + (i < n? B[i] : 0) > x){
			x = (i? A[i - 1] : 0) + (i < n? B[i] : 0);
			a = i - (i? A[i - 1] : 0); b = t - (i < n? B[i] : 0);
		}
	}
}

int main()
{
	int i, _x, _a, _b;
	
	scanf("%s%s", S1, S2);
	
	n = strlen(S1); m = strlen(S2);
	
	for(i=0; i<=m; i++){
		_x = 0; _a = 0; _b = 0;
		f(i, _x, _a, _b);
		if(_x > x) x = _x, a = _a, b = _b;
	}
	
	reverse(S1, S1 + n);
	
	for(i=0; i<=m; i++){
		_x = 0; _a = 0; _b = 0;
		f(i, _x, _a, _b);
		if(_x > x) x = _x, a = n - _a - x, b = _b;
	}
	
	printf("%d\n%d %d\n", x, a, b);
	
	return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s", S1, S2);
  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 376 KB Output is correct
2 Correct 191 ms 504 KB Output is correct
3 Correct 274 ms 400 KB Output is correct
4 Correct 175 ms 432 KB Output is correct
5 Correct 147 ms 376 KB Output is correct
6 Correct 163 ms 432 KB Output is correct
7 Correct 173 ms 504 KB Output is correct
8 Correct 208 ms 504 KB Output is correct
9 Correct 217 ms 376 KB Output is correct