首页 > 其他分享 >字符串指南

字符串指南

时间：2024-09-19 19:01:51浏览次数：9  
标签：指南 MOD1 MOD2 return int MAXN ull 字符串

kmp

kmp 是模式串匹配的算法，本来最坏时间复杂度可以达到 $\operatorname{O}(n\times m)$，但是 kmp 可以将复杂度优化到 $\operatorname{O}(n+m)$。

kmp 有个很重要的东西，叫做 $nxt$ 失配数组。比如对于一个字符串 $s$，它的失配数组 $nxt_n$ 就是 $s$ 的最大前缀等于后缀的长度。$\operatorname{O}(n\times m)$ 的算法的劣势在于每一次失配都要重头，但是 kmp 是从上一次最大失配数组 $nxt_{nxt_n}$ 开始匹配的，这样会优化很多无意义匹配的时间。

设定一个 $pos$ 为匹配开始的位置，然后通过 $nxt$ 数组来跳，可以达到 $\operatorname{O}(n+m)$ 的时间复杂度。

int len1=strlen(s1+1);
int len2=strlen(s2+1);
int pos=0;
for(int i=2;i<=len2;++i){
	while(pos&&s2[i]!=s2[pos+1]){
		pos=nxt[pos];//跳 nxt 
	}
	if(s2[i]==s2[pos+1]){
		++pos;//匹配成功 
	}
	nxt[i]=pos;//存入 nxt 
}
pos=0;
for(int i=1;i<=len1;++i){
	while(pos&&s1[i]!=s2[pos+1]){
		pos=nxt[pos];//跳 nxt 
	}
	if(s1[i]==s2[pos+1]){
		++pos;//匹配成功 
	}
	if(pos==len2){
		printf("%d %d\n",i,i+len2-1);//一个位置 
	}
}

例题

首先求出 nxt 数组，然后在 nxt 数组上 dp，设 $dp_i$ 表示前缀 $i$ 的答案，只可能从 $dp_{nxt_i}$ 和 $dp_i$ 转移过来，具体开桶实现。

#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
char s[MAXN];
int nxt[MAXN],dp[MAXN],mp[MAXN];
int main(){
	scanf("%s",s+1);
	int len=strlen(s+1);
	int pos=0;
	for(int i=2;i<=len;++i){
		while(pos&&s[i]!=s[pos+1]){
			pos=nxt[pos];
		}
		if(s[i]==s[pos+1]){
			++pos;
		}
		nxt[i]=pos;
	}
	for(int i=1;i<=len;++i){
		dp[i]=i;
		if(mp[dp[nxt[i]]]>=i-nxt[i]){
			dp[i]=dp[nxt[i]];
		}
		mp[dp[i]]=i;
	}
	printf("%d",dp[len]);
	return 0;
}

字符串哈希

字符串哈希的思想是，通过把字符串看做 $k$ 进制数来进行存储和比较。

  • 优点：相较于直接字符比较，更加迅速，而且能够 $\operatorname{O}(1)$ 查询某段子区间的哈希值。
  • 缺点：容易冲突。

为了应对冲突，我们需要对哈希进制做一些优化，模数也需要非常极品。下面，给出预处理模版代码。

typedef unsigned long long ull;
ull base[MAXN],pre[MAXN],suf[MAXN];//进制、前缀哈希、后缀哈希
int len;
char s[MAXN];
inline ull get_pre(int l,int r){//O(1) 查询子区间哈希值 
	return ((pre[r]-pre[l-1]*base[r-l+1])%MOD+MOD)%MOD;
} 
inline ull get_suf(int l,int r){//O(1) 查询子区间哈希值 
	return ((suf[l]-suf[r+1]*base[r-l+1])%MOD+MOD)%MOD;
}
inline void prework(){
	base[0]=1;
	for(int i=1;i<MAXN;++i){
		base[i]=(base[i-1]*HASH)%MOD;
	}
	for(int i=1;i<=len;++i){
		pre[i]=(pre[i-1]*HASH+s[i]+DIF)%MOD;//加上偏移量防卡 
	}
	for(int i=len;i>=1;--i){
		suf[i]=(suf[i+1]*HASH+s[i]+DIF)%MOD;//加上偏移量防卡 
	}
}

有时候，可以采取双模哈希来进行防卡，这样被卡的几率很小。

typedef unsigned long long ull;
ull base1[MAXN],pre1[MAXN],suf1[MAXN];
ull base2[MAXN],pre2[MAXN],suf2[MAXN];//进制、前缀哈希、后缀哈希
int len;
char s[MAXN];
inline ull get_pre1(int l,int r){
	return ((pre1[r]-pre1[l-1]*base1[r-l+1])%MOD1+MOD1)%MOD1;
} 
inline ull get_suf1(int l,int r){
	return ((suf1[l]-suf1[r+1]*base1[r-l+1])%MOD1+MOD1)%MOD1;
}
inline ull get_pre2(int l,int r){//O(1) 查询子区间哈希值 
	return ((pre2[r]-pre2[l-1]*base2[r-l+1])%MOD2+MOD2)%MOD2;
} 
inline ull get_suf2(int l,int r){
	return ((suf2[l]-suf2[r+1]*base2[r-l+1])%MOD2+MOD2)%MOD2;
}
inline void prework(){
	base1[0]=base2[0]=1;
	for(int i=1;i<MAXN;++i){
		base1[i]=(base1[i-1]*HASH1)%MOD1;
		base2[i]=(base2[i-1]*HASH2)%MOD2;
	}
	for(int i=1;i<=len;++i){
		pre1[i]=(pre1[i-1]*HASH1+s[i]+DIF1)%MOD1;
		pre2[i]=(pre2[i-1]*HASH1+s[i]+DIF2)%MOD2;//加上偏移量防卡 
	}
	for(int i=len;i>=1;--i){
		suf1[i]=(suf1[i+1]*HASH1+s[i]+DIF1)%MOD1;
		suf2[i]=(suf2[i+1]*HASH2+s[i]+DIF2)%MOD2;//加上偏移量防卡 
	}
}

例题

这一道题目可以先把哈希值处理出来，然后发现可以枚举中间点，然后向左右二分。由于向左延伸 $n$ 格是回文串，那么 $n-1$ 格肯定也是回文串。所以满足单调性可以二分。由于本题有 Hack 数据卡自然溢，所以要打双模。

#include<bits/stdc++.h>
#define MAXN 500005
#define HASH1 31
#define HASH2 29
#define MOD1 193910017
#define MOD2 1000000009
#define ADD 131 
using namespace std;
typedef long long ull; 
int len;
char s[MAXN];
ull base1[MAXN],pre1[MAXN],suf1[MAXN];
ull base2[MAXN],pre2[MAXN],suf2[MAXN];
inline ull get_pre1(int l,int r){
	if(!l){
		return 0;
	}
	return ((pre1[r]-pre1[l-1]*base1[r-l+1])%MOD1+MOD1)%MOD1;
}
inline ull get_suf1(int l,int r){
	if(!l){
		return 0;
	}
	return ((suf1[l]-suf1[r+1]*base1[r-l+1])%MOD1+MOD1)%MOD1;
}
inline ull get_pre2(int l,int r){
	if(!l){
		return 0;
	}
	return ((pre2[r]-pre2[l-1]*base2[r-l+1])%MOD2+MOD2)%MOD2;
}
inline ull get_suf2(int l,int r){
	if(!l){
		return 0;
	}
	return ((suf2[l]-suf2[r+1]*base2[r-l+1])%MOD2+MOD2)%MOD2;
}
int main(){
	scanf("%d %s",&len,s+1);
	base1[0]=base2[0]=1;
	for(int i=1;i<=len;++i){
		base1[i]=(base1[i-1]*HASH1)%MOD1;
		base2[i]=(base2[i-1]*HASH2)%MOD2;
		pre1[i]=(pre1[i-1]*HASH1+(s[i]-'0'+ADD))%MOD1;
		pre2[i]=(pre2[i-1]*HASH2+(s[i]-'0'+ADD))%MOD2;
	}
	for(int i=len;i>=1;--i){
		suf1[i]=(suf1[i+1]*HASH1+('1'-s[i]+ADD))%MOD1;
		suf2[i]=(suf2[i+1]*HASH2+('1'-s[i]+ADD))%MOD2;
	}
	ull ans=0;
	for(int i=1;i<len;++i){
		int l=0,r=min(i,len-i),res=0;
		if(s[i]==s[i+1]){
			continue;
		}
		while(l<=r){ 
			int mid=(l+r)>>1;
			if(get_pre1(i-mid,i)==get_suf1(i+1,i+1+mid)&&get_pre2(i-mid,i)==get_suf2(i+1,i+1+mid)){
				l=mid+1;
				res=l;
			}else{
				r=mid-1;
			}
		}
		ans+=res;
	}
	printf("%llu",ans);
	return 0;
}

字典树

字典树是一种 $k$ 叉树结构。原理是每一个节点都有一个布尔值 $flag$，判断是否是一个字符串的结尾。每一条边都有一个字符，表示前面的字符拼接起来就是字符串。这种数据结构能够 $\operatorname{O}(n)$ 查找前缀。

int cnt,trie[MAXN][MAXT],flag[MAXN];
inline int turn(char c);//字符映射函数 
inline void insert(string s){
	int root=0;
	for(int i=0;i<s.size();++i){
		int p=turn(s[i]);
		if(trie[root][p]){//有没有节点创建过 
			root=trie[root][p];//有就跳 
		}else{
			root=trie[root][p]=++cnt;//没有就建边 
		}
	}
	flag[root]=true;//标记末尾 
}
inline bool find(string s){
	int root=0;
	for(int i=0;i<s.size();++i){
		int p=turn(s[i]);
		if(!trie[root][p]){//如果没有，直接返回 
			return false;
		} 
		root=trie[root][p];//跳 
	}
	return flag[root];//有没有这个末尾 
}

例题

这一道题目考虑贪心证明。如果在某一层，$u$ 需要比 $v$ 先，那么就建一条边。如果在下一层，出现了需要 $v$ 比 $u$ 先的情况，那就冲突了，不可能是最优。也就是判环或者用种类并查集。用 Topu 或者 Tarjan 都可以判环。

#include<bits/stdc++.h>
#define MAXN 30003
#define MAXM 26
#define MAXK MAXN*10
using namespace std;
struct node{
	int nxt[MAXM];
	bool end;
}tree[MAXK];
vector<string> ans;
int n,cnt,indeg[MAXM];
bool vis[MAXM][MAXM];
string s[MAXN];
inline void insert(string str){
	int root=0;
	for(int i=0;i<str.size();++i){
		int dot=str[i]-'a';
		if(!tree[root].nxt[dot]){
			tree[root].nxt[dot]=++cnt;
		}
		root=tree[root].nxt[dot];
	}
	tree[root].end=true;
}
inline bool addedge(string str){
	int root=0;
	for(int i=0;i<str.size();++i){
		int dot=str[i]-'a';
		if(tree[root].end){
			return false;
		}
		for(int j=0;j<MAXM;++j){
			if(tree[root].nxt[j]&&dot!=j&&!vis[dot][j]){
				++indeg[j];
				vis[dot][j]=true;
			}
		}
		root=tree[root].nxt[dot];
	}
	return true;
}
inline bool topusort(){
	queue<int> q;
	for(int i=0;i<MAXM;++i){
		if(!indeg[i]){
			q.push(i);
		}
	}
	while(!q.empty()){
		int front=q.front();
		q.pop();
		for(int i=0;i<MAXM;++i){
			if(vis[front][i]){
				--indeg[i];
				if(!indeg[i]){
					q.push(i);
				}
			}
		}
	}
	for(int i=0;i<MAXM;++i){
		if(indeg[i]){
			return false;
		}
	}
	return true;
}
int main(){
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>s[i];
		insert(s[i]);
	}
	for(int i=1;i<=n;++i){
		memset(indeg,0,sizeof(indeg));
		memset(vis,0,sizeof(vis));
		if(addedge(s[i])&&topusort()){
			ans.push_back(s[i]);
		}
	}
	cout<<ans.size();
	for(int i=0;i<ans.size();++i){
		cout<<endl<<ans[i];
	}
	return 0;
}

标签：指南,MOD1,MOD2,return,int,MAXN,ull,字符串
From： https://www.cnblogs.com/hisy/p/18421160

相关文章

  • 敏感个人信息识别指南正式版发布，个人信息保护合规要求更明确
    9月14日，全国网络安全标准化技术委员会秘书处发布《网络安全标准实践指南——敏感个人信息识别指南》。2020年发布的国标文件GB/T35273《信息安全技术个人信息安全规范》中提到关于敏感个人信息的示例，本次公开的《敏感个人信息识别指南》详细规定了敏感个人信息的识别规则、常见......
  • Go 入门指南：8.5. map 的排序
     原创 吃个大西瓜 CodingBigTree  2024年09月19日08:00 云南map默认是无序的，不管是按照key还是按照value默认都不排序（详见第8.3节）。如果你想为map排序，需要将key（或者value）拷贝到一个切片，再对切片排序（使用sort包，详见第7.6.6节），然后可以使用切片......
  • Kafka 安全机制详解及配置指南
    个人名片......
  • 大语言模型应用指南：提示的构成
    大语言模型应用指南：提示的构成1.背景介绍1.1问题的由来在当今的AI领域，大语言模型因其出色的自然语言处理能力而受到广泛关注。这些模型通常以海量文本数据为基础进行训练，能够生成连贯、多样化的文本，适用于问答、文本生成、翻译等多个场景。然而，尽管大语言模型具有强大......
  • 在WordPress中最佳Elementor主题推荐：专家级指南
    对于已经在WordPress和Elementor上有丰富经验的用户来说，选择功能强大且高度灵活的主题，能大大提升网站的表现和定制能力。今天，我们来介绍六款适合用户的专家级Elementor主题：Sydney、Blocksy、RifeFree、Customify、Deep和Layers。这些主题不仅功能丰富，还在设计和定制方面提供了极大......
  • 开始你的博客之旅：从零到一的详细指南
    创建博客不仅是表达自我的方式，更是与世界分享知识、塑造个人品牌、甚至实现商业变现的强大工具。本文将详细介绍从确定主题到实际运营的每个步骤，帮助你顺利开启个人博客的旅程。确定博客的主题和目标在开始博客之前，首先要明确博客的主题和目标。选择一个你感兴趣且有一定知识积累的......
  • 数论指南
    同余定理同余性质同余性质是指在任意情况下，都有：$n\timesm\bmodp$=$(n\bmodp)\times(m\bmodp)\bmodp$$n+m\bmodp$=$(n\bmodp)+(m\bmodp)\bmodp$$n-m\bmodp$=$(n\bmodp)-(m\bmodp)\bmodp$除法不满足同余性质。欧拉定理欧拉函数：$\varphi(n)$表示在$1$和$n......
  • 南大通用GBase 8s HAC集群搭建部署指南（下）
    在上篇文章中，我们完成了GBase8sHAC集群搭建的初步配置。本文将重点介绍如何配置主节点和辅节点之间的互信关系，以及如何搭建并验证HAC集群的状态。1、配置互信互信是集群节点间通信的基础。我们可以通过配置.rhosts文件或使用REMOTE_SERVER_CFG参数两种方式来实现互信。根据企业的......
  • 相亲交易系统源码详解与开发指南
    随着互联网技术的发展，越来越多的传统行业开始寻求线上转型，其中就包括婚恋服务。传统的相亲方式已经不能满足现代人快节奏的生活需求，因此，开发一款基于Web的相亲交易系统显得尤为重要。本文将详细介绍如何使用PHP语言构建一个高效、安全的相亲交易系统，并提供部分源代码示例。技术选型......
  • 大人时代变了，ChatGPT使用指南（喂嘴里）
    目录一、面向软件开发人员的ChatGPT提示词二、AI能力对比和推荐三、AI能做什么国外ChatGPT的大模型工具使用对于国内大部分人来说仍然有比较大的门槛，比如网络访问限制问题，账户注册限制，账户封号等问题。那么在国内，有没有一些可替代工具呢？这篇文章就给大家分享一些高效的......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99