一本通字符串 哈希 KMP

#include <stdio.h>
#include <string.h>
typedef unsigned long long ULL;
const int N = 2e6 + 5;
int n, m; char str[N];
ULL p[N][2], h[N][2];
inline ULL hash(int l, int r, bool t) { return h[r][t] - h[l - 1][t] * p[r - l + 1][t]; }
inline bool same(int l1, int r1, int l2, int r2)
{ return hash(l1, r1, 0) == hash(l2, r2, 0) && hash(l1, r1, 1) == hash(l2, r2, 1); }
int main() {
	scanf("%d%s", &n, str + 1), m = n >> 1;
	if(!(n & 1)) return puts("NOT POSSIBLE"), 0;
	for(int i = p[0][0] = p[0][1] = 1; i <= n; i ++)
		p[i][0] = p[i - 1][0] * 23333, h[i][0] = h[i - 1][0] * 23333 + str[i],
		p[i][1] = p[i - 1][1] * 13331, h[i][1] = h[i - 1][1] * 13331 + str[i];
	int res = 0;
	for(int i = 1; i <= m + 1; i ++)
		if(same(1, i - 1, m + 2, m + i) && same(i + 1, m + 1, m + i + 1, n)) res = 1;
	for(int i = 1; i <= m + 1; i ++)
		if(same(1, i - 1, m + 1, m + i - 1) && same(i, m, m + i + 1, n))
			{ if(res == 1 && strncmp(str + 1, str + m + 2, m)) return puts("NOT UNIQUE"), 0; res = -1; }
	if(res == 1) puts(str + m + 2);
	else if(res) str[m+1] = 0, puts(str + 1);
	else puts("NOT POSSIBLE");
	return 0;
}

#include <stdio.h>
#include <string.h>
const int N = 2e5 + 3;
typedef unsigned long long ULL;
int n, a[N], res[N], tot, ans;
ULL p[N], h1[N], h2[N];
// inline ULL hash(int l, int r)
// { return (h1[r] - h1[l - 1] * p[r - l + 1]) ^ (h2[l] - h2[r + 1] * p[r - l + 1]); }
inline ULL hash1(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; }
inline ULL hash2(int l, int r) { return h2[l] - h2[r + 1] * p[r - l + 1]; }
int h[N], nxt[N], idx; ULL key[N];
int stk[N], top;
int insert(ULL _key) {
	int hv = _key % N;
	for(int i = h[hv]; i; i = nxt[i]) if(key[i] == _key) return 0;
	stk[++ top] = hv, key[++ idx] = _key, nxt[idx] = h[hv], h[hv] = idx;
	return 1;
}
int main() {
	scanf("%d", &n);
	for(int i = *p = 1; i <= n; i ++)
		scanf("%d", a + i), p[i] = p[i - 1] * N, h1[i] = h1[i - 1] * N + a[i];
	for(int i = n; i; i --) h2[i] = h2[i + 1] * N + a[i];
	for(int k = 1; k <= n; k ++) {
		int sum = 0;
		for(int i = 0; i + k <= n; i += k)
			if(hash1(i + 1, i + k) == hash2(i + 1, i + k)) sum += insert(hash1(i + 1, i + k));
			else sum += insert(hash1(i + 1, i + k)) && insert(hash2(i + 1, i + k));
		if(sum > ans) res[0] = k, tot = 1, ans = sum;
		else if(sum == ans) res[tot ++] = k;
		idx = 0; while(top) h[stk[top --]] = 0;
	}
	printf("%d %d\n", ans, tot);
	for(int i = 0; i < tot; i ++) printf("%d ", res[i]);
	return 0;
}

// 枚举中间点,二分
#include <stdio.h>
#include <string.h>
const int N = 5e5 + 5;
typedef unsigned long long ULL;
int n; char str[N];
ULL p[N], h1[N], h2[N];
inline ULL hash1(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; }
inline ULL hash2(int l, int r) { return h2[l] - h2[r + 1] * p[r - l + 1]; }
int main() {
	scanf("%d%s", &n, str + 1);
	for(int i = *p = 1; i <= n; i ++)
		p[i] = p[i-1] * 23333, h1[i] = h1[i-1] * 23333 + str[i] * 10;
	for(int i = n; i; i --) h2[i] = h2[i+1] * 23333 + (str[i] ^ 1) * 10;
	long long res = 0;
	for(int i = 1; i < n; i ++) {
		int l = 0, r = i > n - i ? n - i : i;
		while(l < r) {
			int mid = (l + r + 1) >> 1;
			if(hash1(i - mid + 1, i) == hash2(i + 1, i + mid)) l = mid;
			else r = mid - 1;
		}
		res += l;
	}
	printf("%lld\n", res);
	return 0;
}

#include <stdio.h>
#include <string.h>
const int N = 1e6 + 5;
int n, nxt[N], min[N]; char str[N]; // min为最短前后缀
int main() {
	scanf("%d%s", &n, str + 1);
	for(int i = 2, j = 0; i <= n; i ++) {
		while(j && str[i] != str[j + 1]) j = nxt[j];
		if(str[i] == str[j + 1]) j ++;
		nxt[i] = min[i] = j;
	}
	long long res = 0;
	for(int i = 1; i <= n; i ++) {
		if(min[nxt[i]]) min[i] = min[nxt[i]];
		if(min[i]) res += i - min[i];
	}
	printf("%lld\n", res);
	return 0;
}

#include <stdio.h>
#include <string.h>
const int N = 1.5e4 + 5, inf = 0x3f3f3f3f;
int n, k, nxt[N], min[N]; // min[i]为从i到1的路径>=k的最小的
int res; char str[N];
int main() {
	scanf("%s%d", str + 1, &k), n = strlen(str + 1);
	for(int t = 0; t < n; ++ t) {
		nxt[0] = 0, min[0] = inf;
		for(int i = 2, j = 0; i <= n - t; ++ i) {
			while(j && str[t + i] != str[t + j + 1]) j = nxt[j];
			if(str[t + i] == str[t + j + 1]) ++ j;
			nxt[i] = j, min[j] = j < k ? inf : j < min[nxt[j]] ? j : min[nxt[j]];
			if((min[j] << 1) < i) res ++;
		}
	}
	printf("%d\n", res);
	return 0;
}

#include <stdio.h>
#include <string.h>
typedef long long LL;
const int N = 1e6 + 5, mod = 1e9 + 7;
int T, n, nxt[N], num[N]; char str[N];
int main() {
	scanf("%d", &T);
	while(T --) {
		int res = num[1] = 1;
		scanf("%s", str + 1), n = strlen(str + 1);
		for(int i = 2, j = 0; i <= n; ++ i) {
			while(j && str[i] != str[j + 1]) j = nxt[j];
			str[i] == str[j + 1] && (++ j);
			nxt[i] = j, num[i] = num[j] + 1;
		}
		for(int i = 2, j = 0; i <= n; ++ i) {
			while(j && str[i] != str[j + 1]) j = nxt[j];
			str[i] == str[j + 1] && (++ j);
			while((j << 1) > i) j = nxt[j]; // 递推找到第一个满足条件的
			res = LL(num[j] + 1) * res % mod;
		}
		printf("%d\n", res);
	}
	return 0;
}

// 每次尝试除掉最小因数
// 如果[l,r-c]=[l+c,r]则c为循环节
#include <stdio.h>
#include <string.h>
const int N = 5e5 + 5;
typedef unsigned long long ULL;
int n, m; char str[N];
ULL p[N], h[N];
inline ULL hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
int primes[N], minpf[N], cnt;
int main() {
	scanf("%d%s%d", &n, str + 1, &m);
	for(int i = *p = 1; i <= n; i ++)
		p[i] = p[i - 1] * 23333, h[i] = h[i - 1] * 23333 + str[i];
	for(int i = 2; i <= n; i ++) {
		if(!minpf[i]) primes[cnt ++] = minpf[i] = i;
		for(int j = 0; i * primes[j] <= n; j ++) {
			minpf[i * primes[j]] = primes[j];
			if(i % primes[j] == 0) break;
		}
	}
	for(int k = 0, l, r, len, ans; k < m; k ++) {
		scanf("%d%d", &l, &r), len = ans = r - l + 1;
		while(len > 1) {
			if(hash(l, r - ans / minpf[len]) == hash(l + ans / minpf[len], r)) ans /= minpf[len];
			len /= minpf[len];
		}
		printf("%d\n", ans);
	}
	return 0;
}