Submission #544748

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544748	2022-04-02T16:26:03 Z	rainboy	Necklace (Subtask 4) (BOI19_necklace4)	C	15 / 15	251 ms	340 KB

necklace

#include <stdio.h>
#include <string.h>

#define N	3000
#define M	3000

int ff[N + 1 + M];

void kmp(char *aa, int n) {
	int i, j;

	ff[0] = 0;
	for (i = 0, j = 1; j < n; i++, j++) {
		while (aa[i] != aa[j]) {
			if (i == 0) {
				i = -1;
				break;
			}
			i = ff[i - 1];
		}
		ff[j] = i + 1;
	}
}

int n, m, l_, i_, j_;

void solve(char *aa, char *bb) {
	static char cc[N + 1 + M + 1];
	static int pp[M], qq[M];
	int p, i, j;

	for (p = 0; p < n; p++) {
		for (i = p; i < n; i++)
			cc[i - p] = aa[i];
		cc[n - p] = ' ';
		for (j = 0; j < m; j++)
			cc[n - p + 1 + j] = bb[j];
		cc[n - p + 1 + m] = 0;
		kmp(cc, n - p + 1 + m);
		for (j = 0; j < m; j++)
			pp[j] = ff[n - p + 1 + j];
		for (i = 0; i < p; i++)
			cc[p - 1 - i] = aa[i];
		cc[p] = ' ';
		for (j = 0; j < m; j++)
			cc[p + 1 + m - 1 - j] = bb[j];
		cc[p + 1 + m] = 0;
		kmp(cc, p + 1 + m);
		for (j = 0; j < m; j++)
			qq[j] = ff[p + m - 1 - j];
		for (j = 0; j < m; j++)
			if (l_ < pp[j] + qq[j]) {
				l_ = pp[j] + qq[j], i_ = p - qq[j], j_ = j - pp[j] + 1;
			}
	}
}

int main() {
	static char aa[N + 1], bb[M + 1];
	int r, i, j;

	scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
	l_ = 0, i_ = -1, j_ = -1;
	for (r = 0; r < 2; r++) {
		char tmp;

		solve(aa, bb);
		j_ = m - 1 - (j_ + l_ - 1);
		for (i = 0, j = m - 1; i < j; i++, j--)
			tmp = bb[i], bb[i] = bb[j], bb[j] = tmp;
	}
	printf("%d\n", l_);
	printf("%d %d\n", i_, j_);
	return 0;
}

Compilation message

necklace.c: In function 'main':
necklace.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
      |  ^~~~~~~~~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	225 ms	340 KB	Output is correct
2	Correct	184 ms	340 KB	Output is correct
3	Correct	251 ms	340 KB	Output is correct
4	Correct	158 ms	340 KB	Output is correct
5	Correct	127 ms	328 KB	Output is correct
6	Correct	147 ms	340 KB	Output is correct
7	Correct	162 ms	340 KB	Output is correct
8	Correct	184 ms	340 KB	Output is correct
9	Correct	194 ms	340 KB	Output is correct