首页 > 其他分享 >BZOJ 3277 串 题解

BZOJ 3277 串 题解

时间：2024-09-22 21:35:26浏览次数：1  
标签：int 题解 rep mid 3277 res sa rk BZOJ

Statement

给 \(n\) 个串，问每个串有多少子串是所有 \(n\) 个串中至少 \(k\) 个串的子串。

Solution 1

%% 注意到 \(\text{LCP}\) 在后缀排序后一定是连续的一段，包含一个串的区间是连续的

先预处理出对于所有左端点 \(l\)，最左的 \(r\) 满足 \([l..r]\) 中出现了至少 \(k\) 个串的后缀。

特判 \(k=1\)

那么在 height 图上，就可以单调栈处理出左边第一个 \(<\) 他、右边第一个 \(\le\) 他的位置

设 \(i\) 管理的区间为 \([l..r]\)，则他长度为 \(\max(\text{height}(l-1),\text{height}(r+1))+1\sim \text{height}(i)\) 的前缀都做一次贡献

区间加、单点查，树状数组维护即可

\(O(n\log n)\) %%

对于每个后缀，二分他最右的满足条件的前缀，这就是他贡献多少次。

设二分的 \(x\)，可以二分找出 height 上左边、右边第一个 \(<\) 他的位置

同样预处理对于所有 \(l\)，最左的 \(r\) 满足 \([l..r]\) 中出现了至少 \(k\) 个串的后缀。

找到管辖区间 \([l..r]\) 后就可以 \(O(1)\) 判了。

\(O(n\log^2 n)\)

Solution 2

考虑优化

考虑到原串中若后缀 \(i-1\) 有 \(x\) 个前缀是至少 \(k\) 个串的子串，那么后缀 \(i\) 有至少 \(x-1\) 个前缀是至少 \(k\) 个串的子串

按这样的方式算，是 \(O(n\log n)\)

Solution 3

建广义 SAM

设 \(p(u)\) 为 \(u\) 来自哪个串，\(u\) 的出现次数就是他的子树内 \(p\) 的种类数，这就是 HH 的项链

然后对于每个串的答案，在 SAM 上走一遍，每次若出现次数 \(<k\) 就一直跳 \(\text{link}\)，直到出现次数 \(\ge k\) 然后给答案加上 \(\text{len}(u)\).

\(O(n\log n)\)

Code 1

log^2

// log^2
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 2e5 + 10, LN = 20;
string T, s[N];
int n, m = 27, p, t, k, sa[N], rk[N], se[N], cnt[N], height[N], belongs[N], suffixlength[N];

void Rsort() {
	rep(i, 1, m) cnt[i] = 0;
	rep(i, 1, n) ++cnt[rk[i]];
	rep(i, 1, m) cnt[i] += cnt[i - 1];
	reo(i, n, 1) sa[cnt[rk[se[i]]]--] = se[i];
}
void SA() {
	if (n == 1) return (void)(sa[1] = rk[1] = 1);
	rep(i, 1, n) rk[i] = ('a' <= T[i - 1] && T[i - 1] <= 'z') ? (T[i - 1] - 'a' + 1) : 27, se[i] = i;
	Rsort();
	for (int w = 1; w < n; w <<= 1, m = p) {
		p = 0;
		rep(i, n - w + 1, n) se[++p] = i;
		rep(i, 1, n) if (sa[i] > w) se[++p] = sa[i] - w;
		Rsort(), swap(rk, se), p = 0;
		rep(i, 1, n)
			if (se[sa[i]] == se[sa[i - 1]] && se[sa[i] + w] == se[sa[i - 1] + w]) rk[sa[i]] = p;
			else rk[sa[i]] = ++p;
		if (p == n) break;
	}
}
void Getheight() {
	int h = 0;
	rep(i, 1, n) {
		if (h) --h;
		while (T[i + h - 1] == T[sa[rk[i] - 1] + h - 1]) ++h;
		height[rk[i]] = h;
	}
}
int ln, Mn[N][LN];
void initST() {
	ln = __lg(n);
	rep(i, 1, n) Mn[i][0] = height[i];
	rep(j, 1, ln)
		rep(i, 1, n - (1 << j) + 1) Mn[i][j] = min(Mn[i][j - 1], Mn[i + (1 << (j - 1))][j - 1]);
}
int AskMn(int l, int r) {
	int g = __lg(r - l + 1);
	return min(Mn[l][g], Mn[r - (1 << g) + 1][g]);
}

ll ans[N];
int f[N];
void initF() {
	int r = 0;
	vector<int> buc(t + 1, 0);
	buc[0] = 114514;
	int res = 0;
	rep(l, 1, n) {
		while (r < n && res < k) {
			if (!buc[belongs[sa[++r]]]++) ++res;
		}
		if (res >= k) f[l] = r;
		else f[l] = 2e9;
		if (!--buc[belongs[sa[l]]]) --res;
	}
}
void Solve() {
	rep(i, 1, n) {
		int len = suffixlength[sa[i]];
		auto check = [&](int x) {
			int L = 1, R = n;
			{
				int l = 2, r = i, mid = 0, res = 1;
				while (l <= r) {
					mid = (l + r) >> 1;
					if (AskMn(mid, i) < x) res = mid, l = mid + 1;
					else r = mid - 1;
				}
				L = res;
			}
			{
				int l = i + 1, r = n, mid = 0, res = n + 1;
				while (l <= r) {
					mid = (l + r) >> 1;
					if (AskMn(i + 1, mid) < x) res = mid, r = mid - 1;
					else l = mid + 1;
				}
				R = res - 1;
			}
			return R >= f[L];
		};
		int l = 1, r = len, mid = 0, res = 0;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (check(mid)) res = mid, l = mid + 1;
			else r = mid - 1;
		}
		ans[belongs[sa[i]]] += res;
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> t >> k;
	rep(i, 1, t) {
		cin >> s[i], T += s[i];
		if (i != t) T += '#';
	}
	n = T.length(), SA(), Getheight(), initST();
	int pos = 1;
	rep(i, 1, t) {
		int len = s[i].length();
		rep(j, pos, pos + len - 1)
			belongs[j] = i, suffixlength[j] = pos + len - 1 - j + 1;
		pos = pos + len + 1;
	}
	initF(), Solve();
	rep(i, 1, t) cout << ans[i] << " \n"[i == t];
	return 0;
}

Code 2

log，后缀数组

// log
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 4e5 + 10, LN = 20;
string s[N], T;
int n, m = 27, p, t, k, sa[N], rk[N], se[N], cnt[N], height[N];

void Rsort() {
	rep(i, 1, m) cnt[i] = 0;
	rep(i, 1, n) ++cnt[rk[i]];
	rep(i, 1, m) cnt[i] += cnt[i - 1];
	reo(i, n, 1) sa[cnt[rk[se[i]]]--] = se[i];
}
void SA() {
	if (n == 1) return (void)(sa[1] = rk[1] = 1);
	rep(i, 1, n) rk[i] = ('a' <= T[i - 1] && T[i - 1] <= 'z') ? (T[i - 1] - 'a' + 1) : 27, se[i] = i;
	Rsort();
	for (int w = 1; w < n; w <<= 1, m = p) {
		p = 0;
		rep(i, n - w + 1, n) se[++p] = i;
		rep(i, 1, n) if (sa[i] > w) se[++p] = sa[i] - w;
		Rsort(), swap(rk, se), p = 0;
		rep(i, 1, n)
			if (se[sa[i]] == se[sa[i - 1]] && se[sa[i] + w] == se[sa[i - 1] + w]) rk[sa[i]] = p;
			else rk[sa[i]] = ++p;
		if (p == n) break;
	}
}
int ln, Mn[N][LN];
void Getheight() {
	int k = 0;
	rep(i, 1, n) {
		if (k) --k;
		while (T[i + k - 1] == T[sa[rk[i] - 1] + k - 1]) ++k;
		height[rk[i]] = k;
	}
}
void initST() {
	ln = __lg(n);
	rep(i, 1, n) Mn[i][0] = height[i];
	rep(j, 1, ln)
		rep(i, 1, n - (1 << j) + 1)
			Mn[i][j] = min(Mn[i][j - 1], Mn[i + (1 << (j - 1))][j - 1]);
}
int AskMn(int l, int r) {
	int k = __lg(r - l + 1);
	return min(Mn[l][k], Mn[r - (1 << k) + 1][k]);
}
int f[N], belongs[N];
void initF() {
	int r = 0;
	vector<int> buc(t + 1, 0);
	buc[0] = 114514;
	int res = 0;
	rep(l, 1, n) {
		while (r < n && res < k) {
			if (!buc[belongs[sa[++r]]]++) ++res;
		}
		if (res >= k) f[l] = r;
		else f[l] = 2e9;
		if (!--buc[belongs[sa[l]]]) --res;
	}
}
ll ans[N];
int Suffixlength[N];

void Solve() {
	int k = 0;
	rep(i, 1, n) {
		if (k) --k;
		int len = s[belongs[i]].length();
		auto check = [&](int x) {
			int L = 1, R = n, pos = rk[i];
			{
				int l = 2, r = pos, mid = 0, res = 1;
				while (l <= r) {
					mid = (l + r) >> 1;
					if (AskMn(mid, pos) < x) res = mid, l = mid + 1;
					else r = mid - 1;
				}
				L = res;
			}
			{
				int l = pos + 1, r = n, mid = 0, res = n + 1;
				while (l <= r) {
					mid = (l + r) >> 1;
					if (AskMn(pos + 1, mid) < x) res = mid, r = mid - 1;
					else l = mid + 1;
				}
				R = res - 1;
			}
			return R >= f[L];
		};
		while (k < n - i + 1 && check(k + 1)) ++k;
		ans[belongs[i]] += min(Suffixlength[i], k);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> t >> k;
	rep(i, 1, t) {
		cin >> s[i];
		T += s[i];
		if (i != t) T += '#';
	}
	n = T.length(), SA(), Getheight(), initST();
	int pos = 1;
	rep(i, 1, t) {
		int len = s[i].length();
		rep(j, pos, pos + len - 1) 
			belongs[j] = i, Suffixlength[j] = pos + len - 1 - j + 1;
		pos = pos + len + 1;
	}
	initF(), Solve();
	rep(i, 1, t) cout << ans[i] << " \n"[i == t];
	return 0;
}

标签：int,题解,rep,mid,3277,res,sa,rk,BZOJ
From： https://www.cnblogs.com/laijinyi/p/18425933

相关文章

  • BZOJ 4310 跳蚤 题解
    Statement把\(S\)分成不超过\(k\)段，使每段的最大子串中的最大串最小。输出这个串。Solution按排名二分这个串，check中从右往左贪心地划分，需要实现\(O(1)\)比较两个子串大小。#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<......
  • BZOJ 4545 DQS 的 trie 题解
    Statement维护一棵树，边权\(\in\{\texttta,\textttb,\textttc\}\)，根为\(1\)，定义这棵树的子串为从\(1\)走到所有点构成的字符串的所有后缀，需要支持以下操作：问当前树的本质不同子串数给一个点添加一棵子树问一个串在当前树中作为子串的出现次数Solution直接广义SAM+......
  • BZOJ 4932 = BZOJ 9434 = LOJ 6070 基因
    Statement问区间本质不同回文串数，强制在线，\(n\le10^5\).其实还有个四倍经验：BZOJ5384.Solution1考虑一个结论：\(s\)的所有回文后缀按长度排序后，可以划分为\(O(\log|s|)\)段等差数列。考虑离线怎么做：移动右端点\(i\)，新增一个串\(s\)，设其上一次出现的起点为\(q\)，则\([q+......
  • 力扣72-编辑距离（Java详细题解）
    题目链接：力扣72-编辑距离前情提要：因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。dp五部曲。1.确定dp数组和i下标的含义。2.确定递推公式。3.dp初始化。4.确定dp的遍历顺序。5.如果没有ac打印dp数组利于debug。每一个dp题目如果都用这五步分析清楚，那么......
  • ABC372 F 题解
    F-TeleportingTakahashi2先把问题转化一下：把环断开成链，复制\((K+1)\)层，每走一步就相当于前进一层：可以想到一个简单的dp：设\(f(i,j)\)表示走到第\(i\)层第\(j\)个位置的方案数。初始化：\(f(0,1)=1\)，其它均为\(0\)，表示Takahashi从第\(0\)层的\(1\)位置......
  • 【题解】「Public NOIP Round #2」找零
    【题解】「PublicNOIPRound#2」找零[官解](PublicNOIPRound#2题解-博客-Qingyu的博客(pjudge.ac))Tag：背包、dp凸优化决策点单调触碰到知识点盲区了，所以来写几笔。首先，由于我们只关心最终状态下\(1\)的最多个数，其实有用的面值只有\(5,1\)（其她的可以当成若干......
  • U389139 至少有一位重复的数字-题解
    题目传送门一、举例说明以\(654923\)为例要判断在\([0,654923]\)区间至少有一位重复的数值的数，可以考虑其补集，即\(\color{red}所有位数均不重复的数\)，用\(N\)减去补集即为结果。首先可以将其分为两种情况。情况一，位数小于\(6\)位。所有位数均不重复的有\(9\time......
  • 【洛谷】P10417 [蓝桥杯 2023 国 A] 第 K 小的和 的题解
    【洛谷】P10417[蓝桥杯2023国A]第K小的和的题解题目传送门题解CSP-S1补全程序，致敬全A的答案，和神奇的预言家。写一下这篇的题解说不定能加CSP2024的RP代码#include<bits/stdc++.h>#definelowbit(x)x&(-x)#defineendl"\n"usingnamespacestd......
  • 【题解】【枚举】—— [NOIP2014 普及组] 比例简化
    【题解】【枚举】——[NOIP2014普及组]比例简化[NOIP2014普及组]比例简化题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.思路解析2.AC代码[NOIP2014普及组]比例简化通往洛谷的传送门题目背景NOIP2014普及组T2题目描述在社交媒体......
  • 题解：AT_abc372_f [ABC372F] Teleporting Takahashi 2
    题意给出一个\(n\)个点的有向图，点\(i\)连向点\((i+1)\)，点\(n\)连向点\(1\)。再给你\(m\)条额外边。你的初始位置为\(1\)，问你移动\(k\)步的不同方案数（仅当路径不同时两个方案不同）。思路先想怎样暴力转移，显然移动\(k\)步到达一个点的方案数为所有跟这个点连边的移......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99