【董晓算法】竞赛常用知识之字符串2

2024-05-13 18:04

本文主要是介绍【董晓算法】竞赛常用知识之字符串2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

本系列是学习了董晓老师所讲的知识点做的笔记

董晓算法的个人空间-董晓算法个人主页-哔哩哔哩视频 (bilibili.com)

 动态规划系列(还没学完)

【董晓算法】动态规划之线性DP问题-CSDN博客

【董晓算法】动态规划之背包DP问题(2024.5.11)-CSDN博客

【董晓算法】动态规划之背包DP与树形DP-CSDN博客

字符串系列

【董晓算法】竞赛常用知识之字符串1-CSDN博客

字典树

作用:

快速插入和查询字符串

插入

儿子数组 ch[p][j] 存储从节点 p沿着j这条边走到的子节点。
边为26个小写字母(a-z)对应的映射值0-25.
每个节点最多可以有26个分叉。例如,ch[0][2]=1,ch[1][0]=2.ch[2][19]=3。

计数数组 cnt[p]存储以节点 p结尾的单词的插入次数

节点编号 idx 用来给节点编号

 1.空 Trie 仅有一个根节点,编号为0。
枚举字符串的每个字符2,从根开始插,

如果有儿子,则p指针走到儿子.
如果没儿子,则 先创建儿子,p指针再走到儿子

3、在单词结束点记录插入次数。

char s[N];
int ch[N][26], cnt[N], idx;
void insert(char* s)
{int p = 0;for (int i = 0; s[i]; i++) {int j = s[i] - 'a';if (!ch[p][j]) ch[p][j] = ++idx;p = ch[p][j];}cnt[p]++;
}
int query(char* s) {int p = 0;for (int i = 0; s[i]; i++) {int j = s[i] - 'a';if (!ch[p][j]) return 0;p = ch[p][j];}return cnt[p];
}

查询和插入最主要的就是if (!ch[p][j]) 后不一样,和查询会返回值

最大异或对

任选两个进行异或运算,得到的结果最大是多少

思路:尽可能走相反位,结果最优(从根到叶的每一条路径都表示一个整数)

const int N = 100010;
int n, a[N];
int ch[N * 31][2], idx;//题目是2的23次void insert(int x) {int p = 0;for (int i = 30; i >= 0; i--) {int j = x >> i & 1; //取出第i位if (!ch[p][j])ch[p][j] = ++idx;p = ch[p][j];}
}
int query(int x) {int p = 0, res = 0;for (int i = 30; i >= 0; i--) {int j = x >> i & 1; //取出第i位if (ch[p][!j]) {res += 1 << i; //累加位权p = ch[p][!j];}else p = ch[p][j];}return res;
}
int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> a[i], insert(a[i]);int ans = 0;for (int i = 1; i <= n; i++)ans = max(ans, query(a[i]));cout << ans;return 0;
}


int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int j = x >> i & 1; //取出第i位
        if (ch[p][!j]) {
            res += 1 << i; //累加位权
            p = ch[p][!j];
        }
        else p = ch[p][j];
    }
    return res;
}

AC自动机 

AC 自动机(简单版) - 洛谷 (luogu.com.cn)

AC自动机是多模式匹配算法。给定 n个模式串和一个主串,查找有多少个模式串在主串中出现过 

步骤

1.构造 Trie 树
先用n个模式串构造一颗Trie 。
Trie 中的一个节点表示一个从根到当前节点的字符串。
根节点表示空串,节点(5表示“s”,节点6表示“sh",节点7表示“she”。
如果节点是个模式串,则打个标记。例如,cnt[7]=1。
2.构造 AC自动机在 Trie 上构建两类边:回跳边和转移边

3.扫描主串匹配

回跳边指向父节点的回跳边所指节点的儿子,从一个节点指向其最长后缀匹配节点

转移边指向当前节点的回跳边所指节点的儿子,从一个节点指向其直接子节点的链接 

 

构树代码就是上面字典树的代码 

构造 AC自动机

void build() {//建AC自动机queue<int> q;for (int i = 0; i < 26; i++)if (ch[0][i])q.push(ch[0][i]);while (q.size()) {int u = q.front(); q.pop();for (int i = 0; i < 26; i++) {int v = ch[u][i];if (v)ne[v] = ch[ne[u]][i], q.push(v);else ch[u][i] = ch[ne[u]][i];}}
}

 查找单词出现次数

 扫描主串,依次取出字符 s[k].
1.i指针走主串对应的节点,沿着树边或转移边走保证不回退。
2.j指针沿着回跳边搜索模式串,每次从当前节点走到根节点,把当前节点中的所有后缀模式串一网打尽,保证不漏解。
3.扫描完主串,返回答案。

int query(char *s){int ans=0;for(int k=0,i=0;s[k];k++){i=ch[i][s[k]-'a'];for(int j=i;j&&~cnt[j];j=ne[j])//~cnt[i]检查cnt是不是-1ans+=cnt[j], cnt[j]=-1;}return ans;
}

KMP和AC自动机对比

这篇关于【董晓算法】竞赛常用知识之字符串2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/986428

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

golang中reflect包的常用方法

《golang中reflect包的常用方法》Go反射reflect包提供类型和值方法,用于获取类型信息、访问字段、调用方法等,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值... 目录reflect包方法总结类型 (Type) 方法值 (Value) 方法reflect包方法总结

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

python常用的正则表达式及作用

《python常用的正则表达式及作用》正则表达式是处理字符串的强大工具,Python通过re模块提供正则表达式支持,本文给大家介绍python常用的正则表达式及作用详解,感兴趣的朋友跟随小编一起看看吧... 目录python常用正则表达式及作用基本匹配模式常用正则表达式示例常用量词边界匹配分组和捕获常用re

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

gitlab安装及邮箱配置和常用使用方式

《gitlab安装及邮箱配置和常用使用方式》:本文主要介绍gitlab安装及邮箱配置和常用使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1.安装GitLab2.配置GitLab邮件服务3.GitLab的账号注册邮箱验证及其分组4.gitlab分支和标签的

Python常用命令提示符使用方法详解

《Python常用命令提示符使用方法详解》在学习python的过程中,我们需要用到命令提示符(CMD)进行环境的配置,:本文主要介绍Python常用命令提示符使用方法的相关资料,文中通过代码介绍的... 目录一、python环境基础命令【Windows】1、检查Python是否安装2、 查看Python的安