rabin-karp 字符串查找算法-编程思维
和一般的比较字符串的方式不同,Rabin-Karp 查找算法通过对子字符串进行 hash,如果在原有字符串中找到了 hash 值相同的字符串,那么继续比较是否是需要查找的字串,一般来讲,如果 hash 操作做的很好的话,那么一般一次匹配就是待查找的子串 基本思想 长度为 \(M\) 的字符串对应着一个 \(R\) 进制的 \(M\) 位数。为了能够使用一张大小为 \(Q\) 的散列表来保存这种类
morethink program
和一般的比较字符串的方式不同,Rabin-Karp 查找算法通过对子字符串进行 hash,如果在原有字符串中找到了 hash 值相同的字符串,那么继续比较是否是需要查找的字串,一般来讲,如果 hash 操作做的很好的话,那么一般一次匹配就是待查找的子串 基本思想 长度为 \(M\) 的字符串对应着一个 \(R\) 进制的 \(M\) 位数。为了能够使用一张大小为 \(Q\) 的散列表来保存这种类
RSA加密算法是一种非对称加密算法,在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的 [1] RSA 加密算法的可靠性源自于对于极大的整数做因数分解很难在有限的时间内得到有效的解,在未来的某一天,随着计算机性能的不断提高,RSA 算法的可靠性可
算法介绍 博耶-摩尔多数投票算法(英语:Boyer–Moore majority vote algorithm),中文常作多数投票算法、摩尔投票算法等,是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。 这一算法应用的问题原型是在集合中寻找可能存在的多数元素,这一元素在输入的序列重复出现并占到了序列元素的一半以上;在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数
PageRank 算法 作为 Google 最早的一个网页排名算法,该算法在早期的搜索引擎中是搜索结果最为准确的,同时也是 Google 发家的一个重要算法。尽管这些年来该算法不再是 Google 对于网页排名的唯一算法,但是它的核心思想还是值得我们去研究一下的。 算法简单描述:首先假定每个网页被引用的概率是相同的,然后通过计算每个网页被其它网页链接的权值进行进一步的概率计算,得到每个页
MD5 or Bcrypt? 摘要 首先是一个错误的认识观念问题,很多人觉得MD5是一个加密算法。不然,他实则是一种摘要算法,也可以叫哈希函数。他的作用是将目标文本转换成具有相同长度、不可逆的杂凑字符串。而加密算法和他恰恰相反,是将目标转换成具有不同长度、可逆的密文。 MD5简介 一般来说由于摘要算法他的单向运算,具有一定的不可逆性也就是说信息无法被还原了,所以成为加密算法中的一个构成部分。
引言 早年,我发现了一种可以用一个整数表示一个序列的数学方法。 下表是3个数字的全排列,有6种情况,编号0到5。 编号 序列 0 0,1,2 1 0,2,1 2 1,0,2 3 1,2,0 4 2,0,1 5 2,1,0 (图片来自网络) 编码 下面介绍如何从序列计算出编号。以2,1,3,0为例。 2 1 3 0 2+0*4=2 1 2 0
限速器 限速器类型 Leaky Bucket:漏桶算法(和令牌桶(token bucket)非常相似)是一种非常简单,使用队列来进行限流的算法。当接收到一个请求时,会将其追加到队列的末尾,系统会按照先进先出的顺序处理请求,一旦队列满,则会丢弃额外的请求。队列中的请求数目受限于队列的大小。 这种方式可以缓解突发流量对系统的影响,缺点是在流量突发时,由于队列中缓存了旧的请求,导致无法处理新的请
Roaring bitmaps 最近看一篇文章,里面涉及到使用roaring bitmaps来推送用户广告并通过计算交集来降低用户广告推送次数。本文给出roaring bitmaps的原理和基本用法,后续给出原文的内容。 本文来自:A primer on Roaring bitmaps: what they are and how they work 目录Roaring bitmaps什么是bi
原文链接:https://gaoyubo.cn/blogs/3ecd1562.html 一、双指针 27. 移除元素 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 package l
一、关于二叉树和堆的基本概念 1、二叉树 每个节点,最多有2个子树的数结构。 左右子树,也是最多有2个子节点。 2、满二叉树 除最后一层外,每个节点都有2个子节点。 3、完全二叉树 存在的节点,和满二叉树的节点完全对应。 4、堆: Max Heap:最大的元素永远在根节点 任一非终端节点数据均不小于其左、右孩子节点。 Min Heap: 最小的元素永远在根节点 任一非终端节点数据均
1、概念 归并排序使用了二分法,归根到底的思想还是分而治之。 拿到一个长数组,将其不停的分为左边和右边两份,然后以此递归分下去。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合 并成一个有序表,称为二路归并。 归并排序是一种稳定的排序方法。 2、举例 1)合并两个有序数组,伪代码 arr_a = [1,4,5,6] a
1、基本思想 取待排序数组第一个数作为参照数,建立left和right数组,left存储小于参照数的数组集合,right存储大于参照数的数组集合,然后分别对left和right进行递归调用排序。 2、举例 [11,2,3,43,23,5,6,9,10] 取任意的一个数为基准数 temp = arr[0] 遍历数组,将比temp小的元素放在temp的左边,比temp大的元素放在temp的右
1、基数排序的应用场景 把一系列单词,按照英文字典的顺序排序,如 a,alice,bob .... 基数排序不具有普适性。 2、定义 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“筒子法”(bucket sort)或bin sort。 顾名思义,它是通过键值的部分资讯,将要排序的元素分配至某些“桶”中,以此达到排序的作用。 基数排序法是稳定
1、插入排序有两种,直接插入排序和希尔排序 2、希尔排序核心思想 希尔排序本质也是一种插入排序,但是是根据简单插入排序进行优化有的一种更加高效的版本,别称是缩小增量排序。 希尔排序的核心思想是将排序数组按照增量进行分组,然后对分组的元素进行直接插入排序,循环缩小分组增量,最后当增量长度为1是排序结束。 3、举例:给不同身高的人进行排序 第一步:分组,找一个间隔分组,间隔取4。间隔通常是总长度
1、思路 对于数组s: 每一轮,遍历数组,比较相邻的两个数,交换位置,大的放后面; 第一轮,得到最大的数,比较len(s) - 1 次 第二轮,得到第二大的数。。。。 第len(s)-1轮,得到第2小和最小的数。 所以要比较len(s)-1 轮。 2、举例 原始数组:[9,5,4,3,2] 第一轮 • 第一次:9>5==>[5,9,4,3,2] •
1. 雪花算法(Snowflake Algorithm) 雪花算法(Snowflake Algorithm)是一种用于生成唯一标识符(ID)的分布式算法。最初由 Twitter 公司开发,用于生成其内部分布式系统中的唯一ID。雪花算法的设计目标是在分布式系统中生成全局唯一的ID,同时保证ID的有序性和趋势递增。 雪花算法生成的ID是64位的整数,分为以下几个部分: 符号位(1位) 为了适配部分
附上我的代码 import java.io.*; import java.util.ArrayList; public class Main { public static void main(String[] args) { File file = new File("D:\\input1.txt"); // 判断文件格式 if (fil