字符串查找----查找算法的选择

首先来对比一下通用的查找算法和字符串查找算法:

各种字符串查找算法的性能特点

算法(数据结构)

优点

二叉查找树(BST)

适用于随机排列的键

2-3树查找(红黑树)

有性能保证

线性探测法(并行数组)

内置类型,缓存散列值

R向单词查找树

适用于较短键和较小的字母表

三向单词查找树

适用于非随机的键

如果空间足够,R向单词查找树的速度是最快的,能够在常数次次数比较内完成查找。对于大型字母表,R向单词查找树所需空间可能无法满足时,三向单词查找树是最佳选择,因为它对字符比较次数是对数级别的,而二叉查找树中的比较次数是对数级别的。散列表也很有用,但它不支持有序性符号表操作,也不支持扩展的字符类API操作。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P1730 最小密度路径(floyd)

很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

9830
来自专栏AI派

TensorFlow修炼之道(2)——变量(Variable)

变量(Variable)是 TensorFlow 中程序处理的共享持久状态的最佳方法。与常量不同的时,常量创建后,值便无法更改,但是变量创建后 可以修改。并且修...

35540
来自专栏程序生活

美团NLP实习面试总结一 基本知识4 数据结构二 NLP相关技术1 LSTM2 介绍实体链接与实体映射3 解释随机游走的原理及作用4 命名实体识别

机会总是留给有准备的人 一 基本知识 1 python 解释下装饰器和生成器的作用以及用法 类的知识点,类与对象,三个输出 2 java HashMap的实现原...

45330
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第四章 寻路(AStar/A星/A*)算法 (中)

上一部分提到了节点(Node),代价(Cost),估价公式等基本概念,有了这些知识铺垫 就可以正式开启寻路之旅了! ? 如上图,这是一个5行8列的网格,黄色节点...

26560
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

453100
来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

16500
来自专栏C/C++基础

迷宫问题(maze problem)——深度优先(DFS)与广度优先搜索(BFS)求解

给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

1.8K20
来自专栏人工智能LeadAI

pytorch入门教程 | 第一章:Tensor

1 pytorch安装 安装pytorch之前,需要安装好python,还没安装过python的宝宝请先移步到廖雪峰的python教程,待安装熟悉完之后,再过来...

433100
来自专栏数据结构与算法

P2280 [HNOI2003]激光炸弹

题目描述 ? 输入输出格式 输入格式: 输入文件名为input.txt 输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示 输...

32850
来自专栏数据结构与算法

UOJ#52. 【UR #4】元旦激光炮(交互)

一种很显然的$log^2n$的做法:首先在$a$中二分,然后再$b,c$中二分。这样可以得到$60$分的好成绩。

8020

扫码关注云+社区

领取腾讯云代金券