perm-xor-preprocess.cpp

// 문제 풀 때 쓰는 경우, 코드 맨 위에 pragma 붙여야 컴파일 된다
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi2")

#include <x86intrin.h>
#define inl static inline
struct Hash {
	inl const ull P=0x8000400200408480, Q=P<<1|P>>63, R=random_device{}();
	inl vector<pair<ull, ull>> V={{}};

	#define perm(x, a, b) _pdep_u64(_pext_u64(x, a), b)
	inl ull shl(ull x) { return perm(x, P, Q) | (x&~P)<<1; }
	inl ull shr(ull x) { return perm(x, Q, P) | (x&~Q)>>1; }
	inl ull shl(ull x, ull n) {
		auto[a,b]=V[n];
		return perm(x, a, b) | perm(x, ~a, ~b);
	}
	inl ull mix(ull x) {
		x=(x+R)*0xA0761D6478BD642F;
		auto y=x*__uint128_t(x^0xE7037ED1A0B428DB);
		return y^y>>64;
	}
	template<class T> inl auto New(T const& S) {
		auto N=size(S);
		while(V.size()<=N) {
			auto[a,b]=V.back();
			V.push_back({shr(a)^P, shl(b)^Q});
		}
		vector<Hash> A(N+1);
		for(int i=0; i<N; i++) A[i+1]=A[i]+S[i];
		return A;
	}

	ull h, n;
	bool operator==(Hash r) const { return h==r.h && n==r.n; }
	Hash operator+(ull c) const { return {shl(h)^mix(c), n+1}; }
	Hash operator+(Hash r) const { return {shl(h, r.n)^r.h, n+r.n}; }
	Hash operator-(Hash l) const { return {h^shl(l.h, n-l.n), n-l.n}; }
};
template<class Fn>
inl int lcp(Fn ok, ull e, ull s=0) { // ok: m번째 문자까지 일치하는지 리턴하는 함수
	auto go=[&](int m) { ok(m) ? s=m+1 : e=m-1; };
	if(e>>4) go(5);
	if(e>>8) go(e-5);
	while(s<e) go(s+e+1>>1);
	return s;
}