腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >Rabin karp字符串匹配算法复杂度

问Rabin karp字符串匹配算法复杂度
EN

Stack Overflow用户

提问于 2014-03-13 09:47:12

回答 1查看 729关注 0票数 1

使用rabin算法中的模是如何帮助降低本地角规则字符串match.Anybody的复杂性的，请解释

string

algorithm

match

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-03-13 11:44:05

我猜Horners规则是指在某个基中将一个字符串作为一个数字来处理("abcd“= 'a‘* p^3 + 'b’* p^2 + 'c‘* p^1 + 'd’* p^0)，并将字符串作为数字进行比较，而Rabin算法指的是本质上相同的东西，而是模一些其他的数字。

问题是使用Horners规则，您只能比较短字符串--否则就会溢出(您可以使用大整数来避免它，但这就是复杂性损失的地方。长度为n的字符串对应的数字将有O(n)位数，因此算术操作不会在O(1)中完成)。

在Rabin算法中，与我们的字符串对应的数字将保持较小，因为我们把它们取为模数。它可能导致碰撞，但如果我们幸运的话，碰撞是足够罕见的。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/22386799

复制

【字符串】字符串查找 ( Rabin-Karp 算法 )

遍历函数面试算法字符串

算法题目链接 : https://www.lintcode.com/problem/13/

韩曙亮

2023/03/29

1.2K0

子字符串查找----Rabin-Karp算法（基于散列）

编程算法

Rabin-Karp算法是一种基于散列的子字符串查找算法--先计算模式字符串的散列值，然后用相同的散列函数计算文本中所有可能的M个字符的子字符串的山裂纸并与模式字符串的散列值比较。如果两者相同，再继续验证两者是否匹配。基本思想：长度为M的对应着一个R进制的M位数，举例说明Rabin-Karp算法：例如要在文本3141592653589793中找到模式26535，首先选择散列表大小Q（这里设置为997），采用除留余数法，散列值为26535%997 = 613，然后计算文本中所有长度为5的字符串的散列值并

SuperHeroes

2018/05/30

2.1K0

别用 KMP 了， Rabin-Karp 算法了解下？

javascript java 编程算法

经常有读者留言，请我讲讲那些比较经典的算法，我觉得有这个必要，主要有以下原因： 1、经典算法之所以经典，一定是因为有独特新颖的设计思想，那当然要带大家学习一波。 2、我会尽量从最简单、最基本的算法切入，带你亲手推导出来这些经典算法的设计思想，自然流畅地写出最终解法。一方面消除大多数人对算法的恐惧，另一方面可以避免很多人对算法死记硬背的错误习惯。我之前用状态机的思路讲解了 KMP 算法，说实话 KMP 算法确实不太好理解。不过今天我来讲一讲字符串匹配的另一种经典算法：Rabin-Karp 算法，这是一个很简单优雅的算法。本文会由浅入深地讲明白这个算法的核心思路，先从最简单的字符串转数字讲起，然后研究一道力扣题目，到最后你就会发现 Rabin-Karp 算法使用的就是滑动窗口技巧，直接套前文讲的滑动窗口算法框架就出来了，根本不用死记硬背。废话不多说了，直接上干货。首先，我问你一个很基础的问题，给你输入一个字符串形式的正整数，如何把它转化成数字的形式？很简单，下面这段代码就可以做到： string s = "8264"; int number = ; for (int i = ; i < s.size(); i++) { // 将字符转化成数字 number = * number + (s[i] - '0'); print(number); } // 打印输出： // 8 // 82 // 826 // 8264 可以看到这个算法的核心思路就是不断向最低位（个位）添加数字，同时把前面的数字整体左移一位（乘以 10）。为什么是乘以 10？因为我们默认探讨的是十进制数。这和我们操作二进制数的时候是一个道理，左移一位就是把二进制数乘以 2，右移一位就是除以 2。上面这个场景是不断给数字添加最低位，那如果我想删除数字的最高位，怎么做呢？比如说我想把 8264 变成 264，应该如何运算？其实也很简单，让 8264 减去 8000 就得到 264 了。这个 8000 是怎么来的？是 8 x 10^3 算出来的。8 是最高位的数字，10 是因为我们这里是十进制数，3 是因为 8264 去掉最高位后还剩三位数。上述内容主要探讨了如何在数字的最低位添加数字以及如何删除数字的最高位，用R表示数字的进制数，用L表示数字的位数，就可以总结出如下公式： /* 在最低位添加一个数字 */ int number = ; // number 的进制 int R = ; // 想在 number 的最低位添加的数字 int appendVal = ; // 运算，在最低位添加一位 number = R * number + appendVal; // 此时 number = 82643 /* 在最高位删除一个数字 */ int number = ; // number 的进制 int R = ; // number 最高位的数字 int removeVal = ; // 此时 number 的位数 int L = ; // 运算，删除最高位数字 number = number - removeVal * R^(L-); // 此时 number = 264 如果你能理解这两个公式，那么 Rabin-Karp 算法就没有任何难度，算法就是这样，再高大上的技巧，都是在最简单最基本的原理之上构建的。不过在讲 Rabin-Karp 算法之前，我们先来看一道简单的力扣题目。高效寻找重复子序列看下力扣第 187 题「重复的 DNA 序列」，我简单描述下题目： DNA 序列由四种碱基A, G, C, T组成，现在给你输入一个只包含A, G, C, T四种字符的字符串s代表一个 DNA 序列，请你在s中找出所有重复出现的长度为 10 的子字符串。比如下面的测试用例：输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC","CCCCCAAAAA"] 解释：子串 "AAAAACCCCC" 和 "CCCCCAAAAA" 都重复出现了两次。输入：s = "AAAAAAAAAAAAA" 输出：["AAAAAAAAAA"] 函数签名如下： List<String> findRepeatedDnaSequences(String s); 这道题的拍脑袋解法比较简单粗暴，我直接穷举所有长度为 10 的子串，然后借助哈希集合寻找那些重复的子串就行了，代码如下： // 暴力解法 List<String> findRepeatedDnaSequences(String s) { int n = s.length(); // 记录出现过的子串 HashSet<String> seen = new HashSet(); // 记录那些重复出现多次的子串 // 注

labuladong

2022/12/08

1K0

常用字符串匹配算法简介

数据处理

字符串模式匹配是常见的算法之一，在实际生活中有较高的使用频率，特别是在当下的互联网服务中，经常用于游戏角色名检查、论坛发帖、直播弹幕、分类打标签、入侵检测等场景。字符串模式匹配又分为单模匹配和多模匹配，区别在于单模匹配是搜索一个模式串，多模式匹配是搜索多个模式串。由于无数大佬前赴后继的投入到模式匹配算法的研究中，时至今日，又有大量成熟的匹配算法，这里姜维大家简要介绍一些，可以根据自身业务需要选用。

用户1257041

2019/09/01

3K0

子字符串查找----各种算法总结

编程算法 java

优点：暴力查找算法：实现简单且在一般情况下工作良好（Java的String类型的indexOf()方法就是采用暴力子字符串查找算法）； Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退； Boyer-Moore算法的性能一般情况下都是亚线性级别； Rabin-Karp算法是线性级别；缺点：暴力查找算法所需时间可能和NM成正比； Knuth-Morris-Pratt算法和Boyer-Moore算法需要额外的内存空间； Rabin-Karp算法内循环很长（若干次算术运算，

SuperHeroes

2018/05/30

1K0

字符串匹配算法_字符串模式匹配算法

编程算法

网络信息中充满大量的字符串，对信息的搜寻至关重要，因此子字符串查找（即字符串匹配）是使用频率非常高的操作：给定一段长度为N的文本和长度为M的模式字符串（N≥M），在文本中找到一个和模式串相匹配的子串。由这个问题可以延伸至统计模式串在文本中出现的次数、找出上下文（和该模式串相符的子字符串周围的文字）等更复杂的问题。

全栈程序员站长

2022/08/02

2.9K0

[数据结构拾遗]子字符串匹配常用算法总结

编程算法

本专栏旨在快速了解常见的数据结构和算法。在需要使用到相应算法时，能够帮助你回忆出常用的实现方案并且知晓其优缺点和适用环境。

蛮三刀酱

2019/03/26

1.2K0

[数据结构拾遗]子字符串匹配常用算法总结

html https 网络安全 java 编程算法

本专栏旨在快速了解常见的数据结构和算法。在需要使用到相应算法时，能够帮助你回忆出常用的实现方案并且知晓其优缺点和适用环境。

Rude3Knife的公众号

2019/08/08

9240

字符串——28. 实现 strStr()

编程算法

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

向着百万年薪努力的小赵

2022/12/02

3070

Miller Rabin算法详解

编程算法深度学习

何为Miller Rabin算法首先看一下度娘的解释(如果你懒得读直接跳过就可以反正也没啥乱用:joy:) Miller-Rabin算法是目前主流的基于概率的素数测试算法，在构建密码安全体系中占有重要的地位。通过比较各种素数测试算法和对Miller-Rabin算法进行的仔细研究，证明在计算机中构建密码安全体系时， Miller-Rabin算法是完成素数测试的最佳选择。通过对Miller-Rabin 算法底层运算的优化，可以取得较以往实现更好的性能。[1] 随着信息技术的发展、网络的普及和电子商务的开

attack

2018/04/11

2.9K0

【字符串】字符串查找 ( 蛮力算法 )

遍历面试算法索引字符串

算法题目链接 : https://www.lintcode.com/problem/13/

韩曙亮

2023/03/29

2.8K0

字符串匹配算法_多字符串匹配

编程算法

从好后缀的后缀子串中，找一个最长的且和模式串的前缀子串匹配的 {v}，滑动至 {v} 对齐

全栈程序员站长

2022/09/25

1.8K0

字符串匹配算法 -- 朴素匹配

编程算法

为什么叫做朴素匹配，我理解的就是这是一种寻常想法，简单粗暴的算法。是一种暴力的算法，不考虑其时间复杂度以及效率。只要达到匹配的目的即可。

lexingsen

2022/02/24

1.9K0

Golang的strings.go源码解析 - Rabin-Karp了解一下？

编程算法

strings包是我们经常在处理字符串的时候要用的，这次我们来看看它其中的一些方法具体是如何实现的。我就找到其中常用的几个方法，然后针对其中比较难的部分还有应用到一些特别算法的部分进行分析。

LinkinStar

2022/09/01

2730

字符串的匹配算法_多字符串匹配

编程算法 https java 网络安全

不要被事物的表面现象所迷惑，这个算法全称：Brute Force，有个拉风的中文名：暴力匹配算法。

全栈程序员站长

2022/09/25

2.2K0

字符串匹配---BF算法--朴素的模式匹配算法

#include<iostream> using namespace std; #include<string> //BF int BF(string& a,string& b) { //求出a串的长度 int sizeA=a.length();//返回的是字符串中字符个数 //求出b串的长度 int sizeB = b.length(); //i指向A，j指向B子串 int i=0; int j=0; //b是子串，a while (i <=sizeA-1&&j<= sizeB-1)

大忽悠爱学习

2021/03/15

2.1K0

KMP（Knuth Morris Pratt）算法的Go语言实现

编程算法

有两部分组成：并且是由大到小，倒着匹配坏前缀：普通匹配只一位一位移动，移动规则为 si(坏字符的位置) xi(坏字符在匹配字符最后出现的位置) 都没有xi=-1 移动距离等于si-xi 好后缀：坏前缀有可能产生负数，所以还要利用好后缀来进行匹配，好后缀类似坏前缀如果匹配串中有和好后缀相同的子串，移动到最靠后的子串的位置，如果没有相同的子串，就需要在匹配的子串中，查找和前缀子串匹配最长的子串进行移动。

ccf19881030

2020/10/28

9220

字符串匹配算法详解

编程算法

愿你们都能考上自己心仪的学校，为你们的备考生涯划上一个完美的句号。做为你们的师兄有几句话想对你们说，希望这些话能对你们有一些帮助。

公众号袁厨的算法小屋

2021/01/08

1.5K0

搜索中常见数据结构与算法探究（二）

数据结构编程算法

Tech 导读本文介绍了几个常见的匹配算法，通过算法过程和算法分析介绍了各个算法的优缺点和使用场景，并为后续的搜索文章做个铺垫；读者可以通过比较几种算法的差异，进一步了解匹配算法演进过程以及解决问题的场景；KMP算法和Double-Array TireTree是其中算法思想的集大成者，希望读者重点关注。 01 前言上文探究了数据结构和算法的一些基础和部分线性数据结构和部分简单非线性数据结构，本文我们来一起探究图论，以及一些字符串模式匹配的高级数据结构和算法。《搜索

京东技术

2022/04/02

3570

【算法】快速排序与归并排序对比

排序数组算法指针字符串

【字符串】最长回文子串 ( 蛮力算法 ) 【字符串】最长回文子串 ( 中心线枚举算法 ) 【字符串】最长回文子串 ( 动态规划算法 ) ★ 【字符串】字符串查找 ( 蛮力算法 ) 【字符串】字符串查找 ( Rabin-Karp 算法 )

韩曙亮

2023/03/29

6370

相似问题

Rabin Karp字符串匹配算法

Karp Rabin算法

Karp-Rabin算法

Rabin-Karp算法

Rabin-Karp字符串匹配算法效率

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问Rabin karp字符串匹配算法复杂度
EN

回答 1

Stack Overflow用户

Rabin Karp字符串匹配算法

Karp Rabin算法

Karp-Rabin算法

Rabin-Karp算法

Rabin-Karp字符串匹配算法效率

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Rabin karp字符串匹配算法复杂度EN

回答 1

Stack Overflow用户

Rabin Karp字符串匹配算法

Karp Rabin算法

Karp-Rabin算法

Rabin-Karp算法

Rabin-Karp字符串匹配算法效率

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问Rabin karp字符串匹配算法复杂度
EN