首页 > 代码库 > acdream1116 Gao the string!(hash二分 or 后缀数组)

acdream1116 Gao the string!(hash二分 or 后缀数组)

2024-07-11 20:05:57   219人阅读

问题套了一个斐波那契数，归根结底就是要求对于所有后缀s[i...n-1]，所有前缀在其中出现的总次数。我一开始做的时候想了好久，后来看了别人的解法才恍然大悟。对于一个后缀来说 s[i...n-1]来说，所有与它匹配的前缀必然是和 s[i+1...n-1]  s[i+2...n-1] ....s[n-1..n-1]里的前缀匹配的，因而如果我们定义一个num[i]表示的是后缀s[i...n-1]与前缀的总长公共前缀，那么num[i]+num[i+1]+..num[n-1]就是前缀在后缀i里出现的次数总和，所以问题转化为求s[i...n-1]跟前缀的最长公共前缀，也可以理解成是  s[0...n-1]和s[i...n-1]求最长公共前缀。

求后缀的最长公共前缀，一个做法是后缀数组，然后建lcp,然后通过rmq询问，理论的复杂度nlogn,我自己套的模板用的是快排，所以后缀数组本身的复杂度就已经是nlog^2n，然后我就愉快的TLE了。

失败之后就只能转而用hash＋二分，毕竟二分还是慢，所以我卡着时限过了这题，心有余悸。

#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <cstdio>#include <vector>#include <cmath>#include <string>#include <algorithm>using namespace std;#define maxn 110000#define ll long long#define mod 1000000007#define step 31/*int rk[maxn], sa[maxn], lcp[maxn];int tmp[maxn];int d[maxn + 50][25];*/int n;/*bool cmp_sa(int i, int j){	if (rk[i] != rk[j]) return rk[i] < rk[j];	else{		int ri = i + k <= n ? rk[i + k] : -1;		int rj = j + k <= n ? rk[j + k] : -1;		return ri < rj;	}}void construct_sa(char *s, int *sa){	n = strlen(s);	for (int i = 0; i <= n; i++){		sa[i] = i;		rk[i] = i < n ? s[i] : -1;	}	for (k = 1; k <= n; k <<= 1){		sort(sa, sa + n + 1, cmp_sa);		tmp[sa[0]] = 0;		for (int i = 1; i <= n; i++){			tmp[sa[i]] = tmp[sa[i - 1]] + (cmp_sa(sa[i - 1], sa[i]) ? 1 : 0);		}		for (int i = 0; i <= n; i++){			rk[i] = tmp[i];		}	}}void construct_lcp(char *s, int *sa, int *lcp){	n = strlen(s);	for (int i = 0; i <= n; i++) rk[sa[i]] = i;	int h = 0;	lcp[0] = 0;	for (int i = 0; i < n; i++){		int j = sa[rk[i] - 1];		for (h ? h-- : 0; i + h < n&&j + h < n&&s[i + h] == s[j + h]; h++);		lcp[rk[i] - 1] = h;	}}void construct_rmq(int *lcp, int sizen){	for (int i = 0; i <= sizen; i++) d[i][0] = lcp[i];	for (int j = 1; (1 << j) <= sizen; j++){		for (int i = 0; (i + (1 << j) - 1) <= sizen; i++){			d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);		}	}}int rmq_query(int l, int r){	if (l > r) swap(l, r); r -= 1;	int k = 0; int len = r - l + 1;	while ((1 << (k + 1)) < len) k++;	return min(d[l][k], d[r - (1 << k) + 1][k]);}*/char s[maxn];ll num[maxn];struct Matrix{	ll a[2][2];	Matrix(){ memset(a, 0, sizeof(a)); }}m;Matrix operator * (const Matrix &a,const Matrix &b){	Matrix ret;	for (int i = 0; i < 2; i++){		for (int j = 0; j < 2; j++){			for (int k = 0; k < 2; k++){				ret.a[i][j] += (a.a[i][k] * b.a[k][j]) % mod;				ret.a[i][j] %= mod;			}		}	}	return ret;}Matrix operator ^ (Matrix a,ll n){	Matrix ret;	for (int i = 0; i < 2; i++) ret.a[i][i] = 1;	while (n){		if (n & 1) ret = ret*a;		n >>= 1;		a = a*a;	}	return ret;}ll cal(ll n){	m.a[0][0] = 0; m.a[0][1] = 1;	m.a[1][0] = 1; m.a[1][1] = 1;	m = m^n;	return m.a[0][1];}ll seed[maxn];ll h[maxn];ll get(int l, int r){	return ((h[r] - h[l - 1] * seed[r - l + 1]%mod) + mod) % mod;}int getlcp(int x){	if (get(1, 1) != get(x, x)) return 0;	int l = 1,r = n - x + 1;	while (l <= r){		int m = (l + r) >> 1;		if (get(1, 1 + m - 1) == get(x, x + m - 1)) l = m+1;		else r = m-1;	}	return r;}int main(){	seed[0] = 1;	for (int i = 1; i < maxn; i++){		seed[i] = seed[i - 1] * step%mod;	}	while (~scanf("%s", s + 1))	{		n = strlen(s + 1); h[0] = 0;		for (int i = 1; i <= n; i++){			h[i] = (h[i - 1] * step + s[i]) % mod;		}		num[1] = n;		for (int i = 2; i <= n; i++){			num[i] = getlcp(i);		}		ll ans = 0;		num[n + 1] = 0;		for (int i = n; i >= 1; i--){			num[i] += num[i + 1];			ans += cal(num[i]);			ans %= mod;		}		printf("%lld\n", ans);	}	return 0;}

 


联系
我们