oj.uz

답안 #930947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930947 2024-02-20T21:18:11 Z rainboy 구간 성분 (KOI15_interval) C
100 / 100
 316 ms 98640 KB 
#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

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 89940 KB Output is correct
2 Correct 61 ms 92548 KB Output is correct
3 Correct 60 ms 91472 KB Output is correct
4 Correct 61 ms 96084 KB Output is correct
5 Correct 61 ms 96184 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 97108 KB Output is correct
2 Correct 75 ms 97104 KB Output is correct
3 Correct 70 ms 96852 KB Output is correct
4 Correct 64 ms 91528 KB Output is correct
5 Correct 78 ms 97104 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 97360 KB Output is correct
2 Correct 147 ms 97264 KB Output is correct
3 Correct 143 ms 97280 KB Output is correct
4 Correct 148 ms 97192 KB Output is correct
5 Correct 148 ms 97364 KB Output is correct
6 Correct 154 ms 97500 KB Output is correct
7 Correct 144 ms 97364 KB Output is correct
8 Correct 144 ms 97364 KB Output is correct
9 Correct 146 ms 97268 KB Output is correct
10 Correct 149 ms 97360 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 97108 KB Output is correct
2 Correct 304 ms 98348 KB Output is correct
3 Correct 284 ms 98236 KB Output is correct
4 Correct 205 ms 97108 KB Output is correct
5 Correct 316 ms 98640 KB Output is correct