Submission #930947

#	Time	Username	Problem	Language	Result	Execution time	Memory
930947		rainboy	구간 성분 (KOI15_interval)	C11	100 / 100	316 ms	98640 KiB

interval

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

#define N	1500
#define M	1500
#define M_	(N * N)
#define A	26
#define MD	0x7fffffff

int max(int a, int b) { return a > b ? a : b; }

int X = 123123123, Y = 456456456, Z = 789789789;

int ppx[A], ppy[A];

void init() {
	int a;
	
	ppx[0] = ppy[0] = 1;
	for (a = 1; a < A; a++) {
		ppx[a] = (long long) ppx[a - 1] * X % MD;
		ppy[a] = (long long) ppy[a - 1] * Y % MD;
	}
}

long long *ek[M_]; int eo[M_];

int hash(long long k) {
	int x = k / MD, y = k % MD;

	return ((long long) x * Z + y) % MD % M_;
}

void ht_add(long long k) {
	int h = hash(k), o;

	for (o = eo[h]; o--; )
		if (ek[h][o] == k)
			return;
	o = eo[h]++;
	if (o >= 2 && (o & o - 1) == 0)
		ek[h] = (long long *) realloc(ek[h], o * 2 * sizeof *ek[h]);
	ek[h][o] = k;
}

int ht_contains(long long k) {
	int h = hash(k), o;

	for (o = eo[h]; o--; )
		if (ek[h][o] == k)
			return 1;
	return 0;
}

int main() {
	static char aa[N + 1], bb[M + 1];
	int n, m, h, i, j, a, x, y, ans;

	init();
	scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
	for (h = 0; h < M_; h++)
		ek[h] = (long long *) malloc(2 * sizeof *ek[h]);
	for (i = 0; i < n; i++) {
		x = y = 0;
		for (j = i; j < n; j++) {
			a = aa[j] - 'a';
			x = ((long long) x + ppx[a]) % MD, y = ((long long) y + ppy[a]) % MD;
			ht_add((long long) x * MD + y);
		}
	}
	ans = 0;
	for (i = 0; i < m; i++) {
		x = y = 0;
		for (j = i; j < m; j++) {
			a = bb[j] - 'a';
			x = ((long long) x + ppx[a]) % MD, y = ((long long) y + ppy[a]) % MD;
			if (ht_contains((long long) x * MD + y))
				ans = max(ans, j - i + 1);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

interval.c: In function 'ht_add':
interval.c:42:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   42 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
interval.c: In function 'main':
interval.c:61:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%s%s", aa, bb), n = strlen(aa), m = strlen(bb);
      |  ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 31 / 31
• Subtask 4: 39 / 39