经典算法:KMP算法
前言
KMP算法全称Knuth-Morris-Pratt字符串查找算法,可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时,本身就包含足够的信息来确定下一个匹配可能的开始位置,此算法利用这一特性以避免重新检查先前配对的字符。
这个算法由高德纳和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。
KMP 算法巧妙地使用了之前的比较数据。它可以在O(n)时间内搜索模式,因为它永远不会重新比较与模式符号匹配的文本符号。但是,它使用部分匹配表来分析模式结构。部分匹配表的构建需要O(m)时间。因此,KMP 算法的整体时间复杂度为O(m n)。
案例
源文本text
:ABCABAABCABAC,需要匹配的字符串pattern
:CAB; 查找是需要同时使用两个循环变量i
,j
。
i:代表源文本字符串text
内匹配字符串pattern
的当前查找位置。
j:代表匹配字符串pattern
当前做比较的字符位置。
图示:
Java代码:
class Main
{
// 实现 KMP 算法
public static void KMP(String text, String pattern)
{
// 匹配文本为null
if (pattern == null || pattern.length() == 0)
{
System.out.println("The pattern occurs with shift 0");
return;
}
// 文本为 NULL,或者源文本的长度小于匹配文本的长度
if (text == null || pattern.length() > text.length())
{
System.out.println("Pattern not found");
return;
}
char[] chars = pattern.toCharArray();
// next[i] 存储下一个最佳部分匹配的索引
int[] next = new int[pattern.length() 1];
for (int i = 1; i < pattern.length(); i )
{
int j = next[i 1];
while (j > 0 && chars[j] != chars[i]) {
j = next[j];
}
if (j > 0 || chars[j] == chars[i]) {
next[i 1] = j 1;
}
}
for (int i = 0, j = 0; i < text.length(); i )
{
if (j < pattern.length() && text.charAt(i) == pattern.charAt(j))
{
if ( j == pattern.length()) {
System.out.println("在索引" (i - j 1) "找到");
}
}
else if (j > 0)
{
j = next[j];
i--; // i将在下一次循环中递增
}
}
}
// 用Java实现KMP算法的程序
public static void main(String[] args)
{
String text = "ABCABAABCABAC";
String pattern = "CAB";
KMP(text, pattern);
}
}
输出:在索引2找到,在索引8找到。
KMP优缺点
KMP最大的优势就是可以保证最坏情况下的效率。预处理时间总是O(n),搜索时间总是O(m)。缺点是在字符串重叠部分不多的情况下,KMP可能并不是那么必要。
参考:cs.indstate.edu/~kmandumula…
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanfbeaf
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24