Submission #67477211

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <string.h>
typedef unsigned long long ull;
#define MOD_BY 2892148736031121531ULL
#define MULT 548571274668263447ULL
#define MULT_INV 1933731169782078360ULL
ull add(ull a, ull b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
ull sub(ull a, ull b) {
  return b == 0 ? a : add(a, MOD_BY - b);
}
ull mul(ull a, ull b) {
  ull r = 0;
  while (b > 0) {
    if (b & 1) r = add(r, a);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

typedef unsigned long long ull;

#define MOD_BY 2892148736031121531ULL
#define MULT 548571274668263447ULL
#define MULT_INV 1933731169782078360ULL

ull add(ull a, ull b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

ull sub(ull a, ull b) {
	return b == 0 ? a : add(a, MOD_BY - b);
}

ull mul(ull a, ull b) {
	ull r = 0;
	while (b > 0) {
		if (b & 1) r = add(r, a);
		a = add(a, a);
		b >>= 1;
	}
	return r;
}

ull mult_pow[512];
ull mult_inv_pow[512];
ull value[512];

ull cache[512][512];

/* [s, e) のハッシュ値を求める */
ull get_hash(int s, int e) {
	if (cache[s][e]) return ~cache[s][e];
	return ~(cache[s][e] = ~mul(sub(value[e], value[s]), mult_inv_pow[s]));
}

int main(void) {
	char S[512];
	int N;
	int i, j, k, ans = 0;
	if (scanf("%511s", S) != 1) return 1;
	N = (int)strlen(S);
	mult_pow[0] = 1;
	mult_inv_pow[0] = 1;
	for (i = 1; i <= N; i++) {
		mult_pow[i] = mul(mult_pow[i - 1], MULT);
		mult_inv_pow[i] = mul(mult_inv_pow[i - 1], MULT_INV);
	}
	for (i = 0; i < N; i++) {
		value[i + 1] = add(value[i], mul((unsigned char)S[i], mult_pow[i]));
	}
	for (i = 2; i < N - 3; i++) { /* S_3 の終わりはどこか */
		for (j = 1; i - j >= 1 && i + 1 + j <= N - 2; j++) { /* S_3 は何文字か */
			if (get_hash(i - j + 1, i + 1) != get_hash(i + 1, i + 1 + j)) continue; /* S_3 != S_4 */
			for (k = 1; i - j - k >= 0 && N - k > i + 1 + j; k++) { /* S_2 は何文字か */
				if (get_hash(i - j - k + 1, i - j + 1) != get_hash(N - k, N)) continue; /* S_2 != S_6 */
				ans++;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

/*

* S_3 の終わりはどこか
* S_3 は何文字か
* S_2 は何文字か

で全探索 O(|S|^3)

*/

Submission Info

Judge Result