BZOJ3238 [Ahoi2013]差异【后缀数组 + 单调栈】

题目链接

题解

简单题

经典后缀数组 + 单调栈套路，求所有后缀\(lcp\)

#include<iostream>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

#include<algorithm>

#define LL long long int

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define cls(s) memset(s,0,sizeof(s))

#define mp(a,b) make_pair<int,int>(a,b)

#define cp pair<int,int>

using namespace std;

const int maxn = 500005,maxm = 100005,INF = 1000000000;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

char s[maxn];

int sa[maxn],rank[maxn],height[maxn],bac[maxn],t1[maxn],t2[maxn],n,m;

void getsa(){

	int *x = t1,*y = t2; m = 255;

	for (int i = 0; i <= m; i++) bac[i] = 0;

	for (int i = 1; i <= n; i++) bac[x[i] = s[i]]++;

	for (int i = 1; i <= m; i++) bac[i] += bac[i - 1];

	for (int i = n; i; i--) sa[bac[x[i]]--] = i;

	for (int k = 1; k <= n; k <<= 1){

		int p = 0;

		for (int i = n - k + 1; i <= n; i++) y[++p] = i;

		for (int i = 1; i <= n; i++) if (sa[i] - k > 0) y[++p] = sa[i] - k;

		for (int i = 0; i <= m; i++) bac[i] = 0;

		for (int i = 1; i <= n; i++) bac[x[y[i]]]++;

		for (int i = 1; i <= m; i++) bac[i] += bac[i - 1];

		for (int i = n; i; i--) sa[bac[x[y[i]]]--] = y[i];

		swap(x,y);

		x[sa[1]] = p = 1;

		for (int i = 2; i <= n; i++)

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		if (p >= n) break;

		m = p;

	}

	for (int i = 1; i <= n; i++) rank[sa[i]] = i;

	for (int i = 1,k = 0; i <= n; i++){

		if (k) k--;

		int j = sa[rank[i] - 1];

		while (s[i + k] == s[j + k]) k++;

		height[rank[i]] = k;

	}

}

cp st[maxn],t;

int top;

void solve(){

	LL sum = 0,ans = 0;

	for (int i = 2; i <= n; i++){

		t = mp(height[i],1);

		while (top && st[top].first >= t.first){

			sum -= 1ll * st[top].first * st[top].second;

			t.second += st[top].second;

			top--;

		}

		st[++top] = t;

		sum += 1ll * t.first * t.second;

		ans += sum;

	}

	printf("%lld\n",1ll * n * (n + 1) * (n - 1) / 2 - 2 * ans);

}

int main(){

	scanf("%s",s + 1); n = strlen(s + 1);

	getsa();

	solve();

	return 0;

}

巴特西

BZOJ3238 [Ahoi2013]差异【后缀数组 + 单调栈】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ3238 [Ahoi2013]差异 【后缀数组 + 单调栈】

题目链接

题解

最新文章

热门文章

BZOJ3238 [Ahoi2013]差异【后缀数组 + 单调栈】