关键词：
【中文标题】匹配一个或零个不匹配的字符串模式【英文标题】：String pattern matching with one or zero mismatch 【发布时间】：2012-04-24 15:39:17 【问题描述】：给定一个要匹配的字符串和一个模式，如何有效地找到零个或一个不匹配的匹配项。
e.g)
S = abbbaaabbbabab
P = abab
Matches are abbb(index 0),aaab(index 4),abbb(index 6),abab(index 10)
我尝试修改 KMP 算法，但我不确定该方法。
请给我解决问题的想法。
谢谢。
【问题讨论】：
S和P的最大长度是多少？ 【参考方案1】：好的，我找到了！我找到了最好的算法！
这听起来有点勇敢，但只要我要提出的算法同时具有运行时间O(m + n) 和内存消耗O(m + n) 并且条目数据本身具有相同的属性，那么算法只能在常数。
使用的算法
我将混合使用 KMP 和 Rabin Karp 算法来解决我的问题。 Rabin Karp 使用rolling hashes 比较初始字符串的子字符串。它需要使用线性附加内存的线性时间预计算，但从那时起，两个字符串的子字符串之间的比较是恒定的O(1)（如果您正确处理冲突，这将摊销）。
我的解决方案不能做什么
我的解决方案不会在第一个字符串中找到 all 匹配第二个字符串最多有 1 个差异的匹配项。但是，可以修改算法，以便对于第一个字符串中的每个起始索引，如果存在这样的匹配，则至少会找到其中一个（这留给读者）。
观察
让m 是第二个字符串的长度，n - 第一个字符串的长度。我将把任务分成两部分：如果我的目标是找到最多有一个差异的匹配项，我想找到第一个字符串的子字符串：PREF 将成为单一差异之前的子字符串，并且SUFF 差后的子串。我想要len(PREF) + len(SUFF) + 1 = m，如果需要，PREF 或SUFF 将被人为缩短（当字符串匹配没有差异时）。
我的解决方案将基于一个非常重要的观察：假设第一个字符串的子字符串从索引i 开始，长度为m，与第二个字符串匹配，最多有一个差异。那么如果我们尽可能长时间地使用PREF，SUFF 的解决方案仍然存在。这很明显：我只是尽可能地将差异推到最后。
算法
现在遵循算法本身。从通常的 KMP 开始。每次当前缀扩展失败并且要遵循失败链接时，首先检查是否跳过下一个字母剩余的后缀是否匹配第二个字符串的剩余部分。如果是这样，则找到最多具有一个字符差异的所寻求的匹配。如果不是 - 我们继续使用普通 KMP 进行 Rabin Karp 检查，每次要遵循失败链接。
让我通过一个示例进一步阐明 Rabin Karp 检查。假设我们在 KMP 的某个步骤，我们发现 first.substring[i, i + k - 1] 匹配第二个字符串的第一个 k 字母。还假设字母first[i + k] 与second[k] 不同。然后使用 Rabin Karp 检查 first.substring[i + k + 1, i + m - 1] 是否与 second.substring[k + 1, m - 1] 完全匹配。这正是您已尽可能扩展起始前缀形式索引i 并且您现在尝试是否存在最多一个差异的匹配的情况。
Rabin Karp 只有在跟随失败链接时才会使用，它将前缀的起始索引至少移动一个，这意味着最多使用O(n) Rabin Karp 调用，每个都具有复杂性O(1)总的线性复杂度。
【讨论】：
我认为当 Text=adbca 和 pattern=eca 时此方法失败。答案应该是 Text[2,4] 但你描述的方法无法检测到它。如果我错了，请纠正我！！！ @ritesh_nitw 你错了。考虑 KMP。让它达到将 Text[2] 与模式的第一个字母进行比较的迭代。失败。所以它尝试使用 Rabin Karp 是否 Text[3,4] == pattern[1,2]。真的。所以它会返回你所期望的。 对不起@Boris Strandjev，我现在明白了。我误读了 Rabin karp 的解释段落。我还要求您在解释中添加一个示例作为编辑，这将很有帮助，因为它是一个不常见且棘手的问题。【参考方案2】：这被称为approximate string matching 问题。在您的特定情况下，您希望最大编辑距离为 1。
bitap algorithm 是一种相当快速的解决方法。
【讨论】：
我认为距离最多为 1 的事实应该允许更快的算法。 我认为bitap算法的运行时间复杂度为O(mn)。有没有 O(m+n) 的算法。谢谢！【参考方案3】：要查找包括一个不匹配在内的所有子匹配，您需要 2 个 z 函数（一个用于原始 P，另一个用于反向 P）。 在原始和反向字符串 S 的最长前缀子匹配的 buld 数组之后。 稍后您需要反转第二个数组。 最后一切都很简单：遍历第一个数组并检查最长前缀的长度是否等于 P 的长度。如果是，那么它是一个没有错误的匹配。 如果它更短，则检查位置 (i + length(P) - 1) 处的第二个数组。如果总和 两个值等于length(P) - 1，那么它是一个错误的子匹配。
复杂度为 O(len(P) + len(S))
【讨论】：
【参考方案4】：Gonzalo Navarro 在他的A guided tour to approximate string matching 中全面概述了各种算法以及它们之间的比较。第 80、81 和 82 页显示了复杂性结果，包括最坏和平均情况，以及各种算法的空间要求。
（在此处使用的符号中，n 表示您搜索的文本的长度，m 表示模式的长度，σ 表示字母的大小，k 表示最大编辑距离，即1 在你的情况下。）
【讨论】：
字符串中匹配数字
importrestring="A1.45，b5，6.45，8.82"print(re.findall(r"d+.?d*",string)) #r"d+.?d*"d+匹配一个或多个数字；.?匹配.一次或零次；d*匹配零个或多个数字#[‘1.45‘,‘5‘,‘6.45‘,‘8.82‘] 查看详情
蚂蚁路径样式模式
...有帮助***.com/q/40886239/355438【参考方案1】：spring-framework中匹配的Ant样式路径模式：映射使用以下规则匹配URL：?匹配一个字符*匹配零个或多个字符**匹配路径中的零个或多个“目录” 查看详情
通配符
通配符通配符描述*匹配任意多个字符（包括零个或一个）?匹配任意一个字符（不包括零个）[characters]匹配任意一个属于字符集中的字符[!characters]匹配任意一个不是字符集中的字符[:class:]匹配任意一个属于指定字符类的字符常使... 查看详情
面试题19：正则表达式匹配（c++）(代码片段)
...的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。题目示例示例1:输入:s="aa"p="a"输出:false解释:"a"无法匹配"aa"整个字符... 查看详情
redis怎样查找一个key？
...有一个keys命令。语法：KEYSpattern说明：返回与指定模式相匹配的所用的keys。该命令所支持的匹配模式如下：（1）?：用于匹配单个字符。例如，h?llo可以匹配hello、hallo和hxllo等；（2）*：用于匹配零个或者多个字符。例如，h*llo可... 查看详情
正则表达式
.：匹配任意一个字符^：匹配以什么开头的字符，如果放在中括号中表示取反，如^abc表示匹配以abc开头的字符，[^abc]表示匹配abc之外的字符$：匹配以什么结尾的字符*：匹配零个或多个星号前面的字符，如abc*可以匹配abc、abcabc、... 查看详情
正则表达式
...1),x2∈L(R2)L(R1|R2)=L(R1)∪L(R2)L(R?)=L(?)∪L(R)∪L(RR)∪··· 匹配符合R的零个或无限多个字符L((R))=L(R)优先级（由高到低）：*，交集，并集括号可以表示组合 缩写字符列表:[a-zA-Z] 匹配括号内任意一个字符非字符列表:[^a-z] ... 查看详情
力扣题目练习一
10.正则表达式匹配给你一个字符串s和一个字符规律p，请你来实现一个支持‘.‘和‘*‘的正则表达式匹配。 ‘.‘匹配任意单个字符 ‘*‘匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖整个字符串s的，而不... 查看详情
列出与模式不匹配的文件？
】列出与模式不匹配的文件？【英文标题】：Listfilesnotmatchingapattern?【发布时间】：2012-01-2111:08:57【问题描述】：以下是如何列出与bash中的模式匹配的所有文件：ls*.jar如何列出模式的补码？即所有不匹配*.jar的文件？【问题讨论... 查看详情
字符串匹配（kmp算法含代码）
主要是针对字符串的匹配算法进行解说有关字符串的基本知识传统的串匹配法模式匹配的一种改进算法KMP算法网上一比較易懂的解说小样例1计算next2计算nextval代码有关字符串的基本知识串（string或字符串）是由零个或多个字符... 查看详情
sourcetree忽略文件
...符号＃开头的行都会被Git忽略。可以使用标准的glob模式匹配。匹配模式最后跟反斜杠（/）说明要忽略的是目录。要忽略指定模式以外的文件或目录，可以在模式前加上惊叹号（!）取反。所谓的glob模式是指shell所使用的简化了的... 查看详情
正则表达式模式匹配顺序
】正则表达式模式匹配顺序【英文标题】：RegularExpressionPatternMatchingorder【发布时间】：2012-06-1702:04:10【问题描述】：在我熟悉的所有语言的正则表达式引擎中，.*表示法表示匹配零个或多个字符。考虑以下Javascript代码：vars="baaab... 查看详情
数据结构—串kmp模式匹配算法(代码片段)
数据结构—串串顺序串代码实现串的模式匹配BF算法代码实现KMP算法代码实现求next数组的代码KMP算法代码改进代码求nextVal修正的KMP算法串串(string)是由零个或多个字符组成的有限序列。含零个字符的串称为空串,用Ø表示。串中所... 查看详情
正则表达式不匹配字符串c＃(代码片段)
...果您计划匹配数字并且反斜杠必须加倍-或更好-使用逐字字符串文字，则d丢失之前的反斜杠。另外，请注意*是一个量词，使其前面的模式匹配0次或更多次。如果需要匹配两个模式之间的任意文本，请使用.*或.*?，如果有换行符... 查看详情
字符串模式匹配kmp算法
字符串模式匹配指的是，找出特定的模式串在一个较长的字符串中出现的位置。朴素的模式匹配算法很直观的可以写出下面的代码，来找出模式串在一个长字符串中出现的位置。/*朴素的模式匹配算法功能：字符串的模式匹配参... 查看详情
ant风格路径表达式
...1，但不匹配/admin或/admin2；*：匹配零个或多个字符串，如/admin*将匹配/admin、/admin123，但不匹配/admin/1；**：匹配路径中的零个或多个路径，如/admin/**将匹配/admin/a或/admin/a/b。ANT通配符有三种：通... 查看详情
用正则表达式怎样匹配不包含特定字符串的字符串
...。。。。求一正则表达式，能匹配所有不含“诺基亚”的字符串正则表达式匹配公式为：^((?!XXX).)*$，XXX为字符串。另外列举一些正则表达式的语法：[abc]a或b或c.任意单个字符a?零个或一个a[^abc]任意不是abc的字符\s空格a*零个或... 查看详情
串串
...零个或多个字符组成的有限序列，又称为我们熟悉的字符串。（回忆内容：。ASCII是由8位二进制数表示一个字符，Unicode是由16位二进制数表示一个字符）串的两种存储结构：顺序存储结构和链式存储结构模... 查看详情