学习
实践
活动
专区
工具
TVP
写文章

KMP字符串查找算法

KMP字符串查找算法 概述 算法的基本思想是:当出现不匹配时,就能知晓一部分文本的内容,可以利用这些信息避免将指针回退到所有这些已知的字符串之前。 DFA的数据结构表示为二维数组dfa[R][M],其中R为指定字典中的字符集的个数(比如ASCII为256),M为匹配字符串pat的长度,状态的意思是文本中某个位置i匹配pat的程度,0状态为未匹配状态 ,M状态为终止状态,找到了完整匹配的字符串。 编码实现 用暴力算法实现字符串查找算法 public int search(String txt, String pat) { int i, N = txt.length( 缺点:最坏的情况(在重复性很高的文本中查找重复性很高的模式)在实际应用中很少出现,还不如使用暴力算法来的容易,性能也差不了多少。

68860
  • 广告
    关闭

    新年·上云精选

    热卖云产品新年特惠,2核2G轻量应用服务器9元/月起,更多上云必备产品助力您轻松上云

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

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

    优点: 暴力查找算法:实现简单且在一般情况下工作良好(Java的String类型的indexOf()方法就是采用暴力字符串查找算法); Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退 ; Boyer-Moore算法的性能一般情况下都是亚线性级别; Rabin-Karp算法是线性级别; 缺点: 暴力查找算法所需时间可能和NM成正比; Knuth-Morris-Pratt算法和Boyer-Moore 算法需要额外的内存空间; Rabin-Karp算法内循环很长(若干次算术运算,其他算法都只需要比较字符); 各种字符串查找算法实现的成本总结 算法 版本 最坏情况 一般情况 是否回退 正确性 额外空间需求 暴力算法 -- MN 1.1N 是 是 1 KMP算法 完整的DFA(博客中实现的方法) 2N 1.1N 否 是 MR 仅构造不匹配的状态转换 3N 1.1N 否 是 M 完整版本 3N N/M 是 是 R Boyer-Moore算法 启发式查找不匹配字符 MN N/M 是 是 R Rabin-Karp算法 蒙特卡洛算法 7N 7N 否 是* 1 拉斯维加斯算法 7N* 7N 是 是 1 *

    59500

    字符串匹配常用算法总结

    字符串匹配算法的定义: 文本长度:N 模式字符串长度:M 有效位移:s ? 解决字符串匹配的算法有非常多,目前常用的有以下几种: 暴力查找 KMP 算法 Boyer-Moore算法 Rabin-Karp指纹字符串查找 字符串匹配算法通常分为两个步骤:预处理(Preprocessing Rabin-Karp 参考: https://www.cnblogs.com/tanxing/p/6049179.html 首先计算模式字符串的散列函数, 如果找到一个和模式字符串散列值相同的字符串, 这个过程等价于将模式保存在一个散列表中, 然后在文本中的所有字符串查找. 但不需要为散列表预留任何空间, 因为它只有一个元素. 总结 优点: 暴力查找算法:实现简单且在一般情况下工作良好(Java的String类型的indexOf()方法就是采用暴力字符串查找算法); Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退

    73420

    字符串匹配常用算法总结

    字符串匹配算法的定义: 文本长度:N 模式字符串长度:M 有效位移:s ? 在这里插入图片描述 解决字符串匹配的算法有非常多,目前常用的有以下几种: 暴力查找 KMP 算法 Boyer-Moore算法 Rabin-Karp指纹字符串查找 字符串匹配算法通常分为两个步骤:预处理( Rabin-Karp 参考: https://www.cnblogs.com/tanxing/p/6049179.html 首先计算模式字符串的散列函数, 如果找到一个和模式字符串散列值相同的字符串, 这个过程等价于将模式保存在一个散列表中, 然后在文本中的所有字符串查找. 但不需要为散列表预留任何空间, 因为它只有一个元素. 在这里插入图片描述 总结 优点: 暴力查找算法:实现简单且在一般情况下工作良好(Java的String类型的indexOf()方法就是采用暴力字符串查找算法); Knuth-Morris-Pratt算法能够保证线性级别的性能且不需要在正文中回退

    68820

    字符串中查找_cstring查找字符串

    查询 首先,我们来定义两个概念,主和模式。我们在字符串 A 中查找字符串 B,则 A 就是主,B 就是模式。我们把主的长度记为 n,模式长度记为 m。 由于是在主中查找模式,因此,主的长度肯定比模式长,n>m。因此,字符串匹配算法的时间复杂度就是 n 和 m 的函数。 字符串匹配算法的案例 最后我们给出一道面试中常见的高频题目,这也是对字符串匹配算法进行拓展,从而衍生出的问题,即查找出两个字符串的最大公共字串。 假设有且仅有 1 个最大公共。比如,输入 a = “13452439”, b = “123456”。由于字符串 “345” 同时在 a 和 b 中出现,且是同时出现在 a 和 b 中的最长子。 首先,你需要对于字符串 a 和 b 找到第一个共同出现的字符,这跟前面讲到的匹配算法在主中查找第一个模式字符一样。

    34730

    扩展kmp求最长回文_算法-字符串之最长回文

    中心扩展法 中心扩展法可以说是常规算法的改进。首先我们知道,回文是中心对称的,相比从头到尾遍历字符串的方法,从中间开始向两边扩展,时间会减少一半。 算法思想:把主中的每一个字符当做回文的中心,向两边扩展,求出最长的回文。其中要注意奇数位的回文和偶数位的回文的区别。eg:aba的中心是b,而abba的中心应该是bb。 算法思想:Manacher采用从中间向两边遍历得到最长回文的思想,将原来的主进行扩展,这个算法严格要求对称,只允许有一个中心点。 p[]:数组p保存的是主中以某个字符为中心的最长回文的半径,eg:p[i]存储的是以str[i]为中心的最长回文的半径,这个半径值是在扩展之后的字符串中。 mid:保存得到的回文的中心点。 s是在原来的字符串 s和p的关系 接下来计算p[],这时要用到max和mid。先解释一下最难懂的地方。利用之前计算的回文的信息计算当前的p[i],现则最小的值。

    10220

    字符串匹配:字符串中查找某

    需求 我们在平时的软件开发,尤其是嵌入式开发,字符串匹配是非常重要的一个算法。而目前常用的字符串匹配算法有很多,下面就来介绍几个。 具体算法 常规方法 对于字符串存放在字符数组的定长顺序存储结构中,可以利用计数指针指示主和模式当前正在比较的字符位置。算法的基本思路是:从主的第i个字符起和模式的第一个字符比较。 KMP算法又称为克努特—莫里斯—普拉特操作,是一种效率非常高的字符串匹配算法。 KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式与主的匹配次数以达到快速匹配的目的。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。 而KMP算法将最长前-后缀概念用在了next数组上。 next 数组各值的含义:代表当前字符之前的字符串中,有多大长度的相同前缀后缀。

    14830

    字符串——459. 重复的字符串

    1 题目描述 给定一个非空的字符串 s ,检查是否可以通过由它的一个重复多次构成。 (或 “abcabc” 重复两次构成。) 由于1 ≤ n’≤ n,那么如果将两个s连在一起,并移除第一个和最后一个字符,那么得到的字符串—定包含s,即s是它的一个。 如果s是该字符串,那么s就满足题目要求。 证明需要使用一些同余运算的小技巧,可以见方法三之后的「正确性证明」部分。这里先假设我们已经完成了证明,这样就可以使用非常简短的代码完成本题。 复杂度分析 由于我们使用了语言自带的字符串查找函数,因此这里不深入分析其时空复杂度。 方法二::KMP 算法 由于本题就是在一个字符串中查询另一个字符串是否出现,可以直接套用 KMP 算法

    12120

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

    ,对信息的搜寻至关重要,因此字符串查找(即字符串匹配)是使用频率非常高的操作:给定一段长度为N的文本和长度为M的模式字符串(N≥M),在文本中找到一个和模式相匹配的。 由这个问题可以延伸至统计模式在文本中出现的次数、找出上下文(和该模式相符的字符串周围的文字)等更复杂的问题。 Boyer-Moore算法 当可以在文本字符串中回退时,如果从右向左扫描模式字符串并将它和文本匹配,那么就能得到一种非常快的字符串查找算法——Boyer-Moore算法。 ,然后计算文本中所有长度为5个数字的字符串中的散列值并寻找匹配。 最坏情况下,文本中所有长度为m的(一共N-M+1个)都和模式匹配,所以算法复杂度为O((N-M+1)m)。

    30320

    字符串查找----Rabin-Karp算法(基于散列)

    Rabin-Karp算法是一种基于散列的字符串查找算法--先计算模式字符串的散列值,然后用相同的散列函数计算文本中所有可能的M个字符的字符串的山裂纸并与模式字符串的散列值比较。 基本思想:长度为M的对应着一个R进制的M位数, 举例说明Rabin-Karp算法: 例如要在文本3141592653589793中找到模式26535,首先选择散列表大小Q(这里设置为997),采用除留余数法 ,散列值为26535%997 = 613,然后计算文本中所有长度为5的字符串的散列值并寻找匹配。 关键思想:实现Rabin-Karp算法关键是要找到一种方法能够快速地计算出文本中所有长度等于要匹配字符串长度的字符串的散列值。也就是对所有位置i,  高效计算出文本中i+1位置的字符串的值。 具体算法为:假设已知h(xi) = xi mod Q, 将模式字符串右移一位等价于将xi替换为x(i+1), x(i+1)等于xi减去第一个数字的值,乘以R,再加上最后一个数字的值。

    1.4K00

    字符串查找之KMP

    当我们需要从文档中查找某个关键词时,就用到了字符串查找技术。比如在某个数据库导出文档中想要查找所有用户的密码,想在一个学长给的word题库中查找你正在做的检测题的答案。 我们可以简单暴力的来实现,从头开始一个字符一个字符的比较字符串文本和模式,如果匹配失败,再从字符串文本的下一个位置开始跟模式从头比较,重复这个过程,如果成功,则返回模式在字符串中的起始位置。 按照暴力算法的逻辑,我们需要将模式向右移一位,也就是模式的第0个字符和字符串文本的第1个字符对齐开始一个一个比对。 也就是说,回退到匹配成功那部分字符串进行的比较,我们只需要模式自己就可以完成。对于文本字符串并不需要任何回退,通过模式自身的信息,我们可以得出,字符串文本的第5个字符应该跟模式的第几个字符串进行比较。 现在唯一的问题就是这个位置是怎么计算出来的,《算法4》中引入了这么个概念——确定有限状态自动机(DFA)。为了方便说明,我们用i来指示字符串文本中字符的位置,j来指示模式中的字符位置。

    24920

    算法字符串

    i是该字符在字符串中的位置; 字符串的长度:字符串中字符的数目n成为字符串的长度; 空串:零个字符构成的也称为「空字符串」,它的长度为0,可以用''表示; 字符串中任意个连续的字符组成序列称为该字符串的 并且有两种特殊,起始于位置为0,长度为k的称为「前缀」,而终止于n-1,长度为k的称为「后缀」; 主:包含字符串相应的称为「主」; 举个例子来说明一下: str = "Hello : 字符串匹配问题 相关问题 前缀 / 后缀相关问题 回文相关问题 序列相关问题 字符串的比较 字符串的比较操作 两个数字之间很容易比较大小,例如 1 < 2。 可以简单理解为,给定字符串 T 和 p,在主 T 中寻找 p。主 T 又被称为 「文本」 , p 又被称为 「模式」 。在字符串问题中,最重要的问题之一就是字符串匹配问题。 其中, Rabin-Karp 算法使用了基于散列的搜索算法 多模式匹配问题 多模式匹配算法大多使用了一种基本的数据结构:「字典树(Trie)」。

    17830

    Java String 过滤字符串

    参考链接: Java字符串之-toUpperCase() Java String 过滤字符串  前几天写到获取Editor值的时候,获取的值(String)中竟然还包含一堆Html的标记.而我不需要或者根本不想要这些标签的存在 第二种是用String类提供的方法,将html标记替换掉,从字符串角度.   第三种是用正则表达式去除带有html标记的富文本,从文本角度,我没有采取这种方法,可能这种方法效率较第二种高.  我们来着重看一下第二种方法:   String 类提供的替换方法:   问题转换成:    过滤掉String(java)中指定的字符串.    我们来看一下[官方文档]中有关字符串内容转换的方法:  String     replace(char oldChar, char newChar)       Returns a new string

    37020

    【题解】字符串(简单版)

    题目描述 查看题目信息 同学们都知道,字符串的概念指的是:用引号“ ”括起来的一有限序列的字符。而字符串就是字符串内的字符序列。 例如,字符串 “abc” 具有如下6个字符串:“a”、“ab”、“abc”(本身也计算在内)、“b”、“bc”、“c”。 现在任意给出一个字符串,请同学们编一个程序输出每个不同的,并统计不同的的个数。 输入格式 文件中只有一行,包含1个任意的字符串字符串中不含空格,其长度L≥5)。 输出格式 文件中共有若干行: 前若干行每行一个字符串为不同的; 最后一行为统计不同的的个数。 要求:每行数据都从第一列开始输出。 substr的用法: s.substr(开始位置,长度) 作用是在原字符串s中获得相应的

    7510

    关注

    腾讯云开发者公众号
    10元无门槛代金券
    洞察腾讯核心技术
    剖析业界实践案例
    腾讯云开发者公众号二维码

    相关产品

    • 文字识别

      文字识别

      文字识别(OCR)基于腾讯优图实验室世界领先的深度学习技术,将图片上的文字内容,智能识别成为可编辑的文本。OCR 支持身份证、名片等卡证类和票据类的印刷体识别,也支持运单等手写体识别,支持提供定制化服务,可以有效地代替人工录入信息。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券