不同子串个数

link

也算是一道模板题了。

上一道题并没有提到的是,后缀数组还有一个很重要的应用,即\(height\)数组,以下简称h。\(h_i\)的定义是排名为i的后缀与排名为i-1的后缀的最长公共前缀长度,而h数组我们可以\(O(N)\)求得。方法如下。

首先有一个结论,\(h[rank[i-1]]-1\le h[rank[i]]\),证明没有看懂,以后看懂了再来填坑。代码如下,先死记硬背吧。

for(int i=1,j;i<=m;h[a[i++]]=hh)
	for(hh?hh--:0,j=pl[a[i]-1];w[i+hh]==w[j+hh];hh++);

还留有一个问题,假如我们已经求出了h数组,那和本题要求的东西有什么关系吗。有,首先字串数量是很好求的,是\(len\times(len+1)/2\)。问题在于其中有多少个字串有重复。可以想到把这些重复子串按照左端点位置进行归类,对于同一类的重复子串,会发现存在一些后缀的某些前缀是相同的,这些一样的前缀即是重复子串,毕竟每一个后缀的前缀集合的并集即是原串的子串集合。而很明显这些前缀相同的后缀会在排序之后分到一起,它们的数量就是h数组所保存的。

代码。

#include<cstdio>
#include<cstring>
//#define zczc
#define ll long long
using namespace std;
const int N=100010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int get(){
	char w=getchar();
	while(w<'a'||w>'z')w=getchar();
	return w-'a'+2;
}
inline int max(int s1,int s2){
	return s1<s2?s2:s1;
}

int m,w[N],a[N];
struct node{
	int id,x,y;
}s[N],r[N];

int maxn,num[N],sum[N];
inline void init(){
	memset(num,0,sizeof(int)*(maxn+2));
	memset(sum,0,sizeof(int)*(maxn+2));
	maxn=0;return;
}
void solve(){
	for(int i=1;i<=m;i++)maxn=max(s[i].y,maxn),num[s[i].y]++;
	for(int i=1;i<=maxn;i++)sum[i]=sum[i-1]+num[i];
	for(int i=1;i<=m;i++)r[sum[s[i].y-1]+(num[s[i].y]--)]=s[i];init();
	for(int i=1;i<=m;i++)maxn=max(maxn,r[i].x),num[r[i].x]++;
	for(int i=1;i<=maxn;i++)sum[i]=sum[i-1]+num[i];
	for(int i=1;i<=m;i++)s[sum[r[i].x]-(--num[r[i].x])]=r[i];
}

int pl[N],h[N],hh;
void workh(){
	for(int i=1,j;i<=m;h[a[i++]]=hh)
		for(hh?hh--:0,j=pl[a[i]-1];w[i+hh]==w[j+hh];hh++);
	return;
}

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);for(int i=1;i<=m;i++)w[i]=a[i]=get();
	for(int n=1;n<=m;n<<=1){
		for(int i=1;i<=m;i++)s[i].id=i,s[i].x=a[i],s[i].y=i+n>m?1:a[i+n];solve();maxn=0;
		for(int i=1;i<=m;i++)a[s[i].id]=(i==1||s[i].x!=s[i-1].x||s[i].y!=s[i-1].y)?++maxn:maxn;
	}
	workh();ll ans=(ll)m*(m-1)>>1;
	for(int i=1;i<=m;i++)ans-=h[i];
	printf("%lld",ans+m);
	
	return 0;
}

一如既往,万事胜意

推荐这些文章:

【墨鳌】【LCP 22. 黑白方格画】

组合数学
\(O(N\cdot M)\)
class Solution {
public:
int f[10][10];

int C(int n, int m) {
if (n == m || m == 0) return 1;
return f[n][m] = C(n - 1, m - 1) + C(n - 1, m);
}

int paintingPlan(int n, int k) {
if (k == 0 || k == n * n) return 1;
int ans = 0;
...

P3374 【模板】树状数组 1

题目传送门
#include <bits/stdc++.h>

using namespace std;

const int N = 5 * 1e5 + 10;
int n, m;
int a[N];

// t[i]表示树状数组i结点覆盖的范围和
int t[N];

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit(int x) {
return x & -x;
}
//将序列中第x个数加上k
void add(int x, int k) {
for (int i = x; i <= n; i += lowb...

在数组中找两个和为s的数的下标,在数组中寻找多个和为sum的数。

在数组中找两个和为s的数的下标
思路
1.用哈希表,扫描数组,放入哈希表中,再一次扫描数组,在哈希表中找s-a[i]。时间复杂度O(n),空间复杂度O(n)
2.-先排序数组,再用前后两个指针向中间找。时间复杂度O(nlogn),空间复杂度O(1),
代码:
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> m = new HashMap<>();
for(int i=0;i<nums.len...

线段树模板 version1.0

struct SegTree{

int treeSize;
vector<long long> sum,v;

void init(int n){
sum.resize(4*n+1);
v.resize(4*n+1);
treeSize=n;
}

inline int ls(int p){
return p<<1;
}

inline int rs(int p){
return p<<1|1;
}

...

#树状数组,dp#SGU 521 North-East

题目
在平面上有 \(n\) 个点,现在有一个人要从某个点出发,
每次只能到达横纵坐标都超过原坐标的点,也就是 \(x_j<x_i,y_j<y_i\)
如果他要经过最多的点,那么哪些点是可能到达的,哪些点是必须到达的。

分析
按横坐标排序,实际上只需要管纵坐标,离散化之后直接用树状数组维护 \(dp[i]=dp[j]+1(y_j<y_i)\)
然后将序列翻转再做一遍,可能到达也就是 \(dp[i]+dp'[i]=ans-1\)
一定到达就是在可能到达的基础上,要保证 \(dp[i]\) 唯一,再统计一下 \(dp[i]\) 的个数即可。

代码
#include <...

codeforces round 782 Div2 D. Reverse Sort Sum

D. Reverse Sort Sum

思路
首先可以观察到每个1都加了n次,所以总共1的个数就是sum/n,然后排完序1都在后面,后面也就好确定,最后一个数字只能有1和n两种情况
1的时候这一位是0,n的时候这一位是1,然后向前移一位,同时把f(a,n)减去,可以使用线段树来维护
代码:
void solve() {
int n = read();
int sum = 0;
for (int i = 1;i <= n;i++) a[i] = read(), sum += a[i];
sum /= n;
build(1, 1, n);
...

【Luogu P2852】[USACO06DEC]Milk Patterns G

链接:
洛谷
题目大意:
给出一个数字串找到一个最大的子串使得其出现次数大于等于 \(k\)。
思路:
简单题。对后缀排序后,求 \(\mathrm{height}\) 数组。那么任意一段区间 \([l,r]\) 后缀的 \(\mathrm{height}\) 的最小值就是它们的 LCP,也是出现次数为 \(r-l+1\) 的最大子串。那么枚举左端点,长度为 \(k\),加 ST 表即可。
代码:
const int N = 2e4 + 10, M = 1e6 + 10;

inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
...

vector<vector<int>>初始化

class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int n=mat.size();
int m=mat[0].size();
vector<vector<int>> ans(n, vector<int>...

最长公共子序列(模板题)

1.今天学了一手最长上升子序(模板题)
 
贴一下代码吧(输出最大路径值与输出路径

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int p[1010];//p数组是记录路径下标
int f[1010];
int n;
void print(int i){//这里是输出路径,递推式,sum值逐渐递减
if(p[i]) print(p[i]);
printf("%d ",a[i]);
}
int main(){
cin>>n;
for(int i=1;i&l...

2031. 1 比 0 多的子数组个数

给你一个只包含 0 和 1 的数组 nums,请返回 1 的数量 大于 0 的数量的子数组的个数。由于答案可能很大,请返回答案对 109 + 7 取余 的结果。
一个 子数组 指的是原数组中连续的一个子序列。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-subarrays-with-more-ones-than-zeros
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
线段树
class Solution {

private static fina...

文章标题:不同子串个数
文章链接:https://www.dianjilingqu.com/50868.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>