模板

int BSGS(int a , int b){
	int y = sqrt(p) + 1;
	gp_hash_table<int , int> mp;
	int t = b;
	for(int n = 0; n <= y; ++ n , t = Mul(t , a)) mp[t] = n;
	int tmp = 1;
	for(int i = 1; i <= y; ++ i , tmp = Mul(tmp , a));
	t = tmp;
	for(int m = 1; m <= y; ++ m , t = Mul(t , tmp)) {
		if(mp.find(t) != mp.end()){
			return m * y - mp[t];
		}
	}
	return -1;
}

int d[N << 1];
int manacher(char* s){
	int len = strlen(s + 1);
	d[1] = 1;
	for(int i = 2 , l = 1 , r = 1; i <= len; ++ i){
		int j = l + r - i , dj = (j ? d[j] : 0);
		d[i] = max(0 , min(dj , j - l + 1));
		if(j - dj + 1 <= l){
			while(i - d[i] >= 1 && i + d[i] <= len && s[i - d[i]] == s[i + d[i]]){
				++ d[i];
			}
			l = i - d[i] + 1 , r = i + d[i] - 1;
		}
	}
	int res = 1;
	for(int i = 1; i <= len; ++ i){
		res = max(res , d[i] - 1);
	}
	return res;
}

const int N = 1e5 + 5;
const int MB = ceil(log2(N)) + 1;
struct S_T {
	int st[50][N] , pw2[50];
	void init(int* a , int n){
		for(int i = 1; i <= n; ++ i){
			st[0][i] = a[i];
		}
		int lim = __lg(n) + 1;
		pw2[0] = 1;
		for(int i = 1; i <= lim; ++ i)pw2[i] = pw2[i - 1] * 2;
		for(int s = 1; s <= lim; ++ s){
			for(int i = 1; i + pw2[s] - 1 <= n; ++ i){
				st[s][i] = max(st[s - 1][i] , st[s - 1][i + pw2[s - 1]]);
			}
		}
	}
	int qwq(int l , int r){
		int LG = __lg(r - l + 1);
		return max(st[LG][l] , st[LG][r - pw2[LG] + 1]);
	}
}ST;

struct S_A {
	int sa[N * 2] , rk[N * 2] , rk1[N * 2] , sz = S , sec[N * 2] , cnt[N * 2];
	void init(){
		for(int i = 1; i <= len; ++ i) rk[i] = c[i] ,  ++ cnt[c[i]];
		for(int i = 1; i <= S; ++ i) cnt[i] += cnt[i - 1];
		for(int i = len; i >= 1; -- i) sa[cnt[rk[i]] -- ] = i;
	}
	void radixsort(){
		for(int i = 0; i <= sz; ++ i) cnt[i] = 0;
		for(int i = 1; i <= len; ++ i) ++ cnt[rk[i]];
		for(int i = 1; i <= sz; ++ i) cnt[i] += cnt[i - 1];
		for(int i = len; i >= 1; -- i) sa[cnt[rk[sec[i]]] -- ] = sec[i] , sec[i] = 0;
	}
	void Sa(){
		init();
		for(int k = 1; k <= len; k *= 2){
			int oo = 0;
			for(int i = len - k + 1; i <= len; ++ i) sec[ ++ oo] = i;
			for(int i = 1; i <= len; ++ i){
				if(sa[i] > k){
					sec[ ++ oo] = sa[i] - k;
				}
			}
			radixsort();
			for(int i = 1; i <= len; ++ i) rk1[i] = rk[i];
			sz = rk[sa[1]] = 1;
			for(int i = 2; i <= len; ++ i){
				if(rk1[sa[i]] == rk1[sa[i - 1]] && 
					rk1[sa[i] + k] == rk1[sa[i - 1] + k]){
					rk[sa[i]] = sz;
				}
				else {
					rk[sa[i]] = ++ sz;
				}
			}
			if(sz == len) return ;
		}
	}
}SA;