Submission #124954

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
124954	2019-07-04T08:04:49 Z	김세빈(#3048)	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	272 ms	504 KB

necklace

#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<t; i++){
		M[i] = 0;
	}
	
	for(i=t; i<m; i++){
		M[i] = t;
	}
	
	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(S2, S2 + m);
	
	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 = m - _b - _x;
	}
	
	printf("%d\n%d %d\n", x, a, b);
	
	return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:65: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

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	504 KB	Output is correct
2	Correct	196 ms	404 KB	Output is correct
3	Correct	272 ms	376 KB	Output is correct
4	Correct	179 ms	504 KB	Output is correct
5	Correct	149 ms	376 KB	Output is correct
6	Correct	163 ms	368 KB	Output is correct
7	Correct	174 ms	504 KB	Output is correct
8	Correct	206 ms	376 KB	Output is correct
9	Correct	216 ms	376 KB	Output is correct