KMP算法
2020-03-17 16:05:00来源:博客园 阅读 ()
KMP算法
Java编写,KMP算法KMP算法
一个专门匹配字符串的算法
e,g
先给出一个 待匹配字符串 B
a b a a b b a b a a b
0 0 1 1 2 0 1 2 3 4 5
// 从 2 个字母开始进行匹配,第一个的F数组值,默认为 0,m 即字符串长度
for(int i = 1; i < m; i++)
{
// j 可以代表将与 B[i] 进行比较的 下标
int j = F[i - 1]
// 当 不匹配 且 待匹配下标对应的数字的 F数组值还大于 1的情况下,进行 j 的前进
// 直到 B[i] 与 B[j] 相等 或者 到了 无对称字母位置
// 例如 aba 中的 b处 此时 j = 0,而j = 0 对应的就是 首字母a,相当于重新开始
while(B[i] != B[j] && j >= 1)
{
j = F[j - 1];
}
// 如果进一步的还继续匹配
if(B[i] == B[j])
F[i] = j + 1; // 下标数组 + 1
else
// 否则 归零
F[i] = 0;
}
利用 F数组寻找匹配,每找到一个匹配就输出其开始的位置
// i 是对应 匹配字符串 A 中的 下标,前进
while(i < n)
{
// 如果 相匹配
if(A[i] == B[j])
{
i++;
j++;
// j 到头了,代表相匹配了,此段
if(j == m)
{
// 如果输出位置是从 1开始标号的
printf("%d\n", i - m + 1);
// 如果输出位置是从 0 开始标号的
printf("%d\n", i - m);
// 这里的 j 再赋值的意义 自己猜吧,提示: A串可能有多个 B
j = F[j - 1] + 1;
}
}
else{
// j == 0 代表B串开头
if(j == 0)
i++;
else
j = F[j - 1];
}
}
利用上面的公式,再来个匹配字符串 A
a b a a b a a b b a b a a a b a a b b a b a a b
B
a b a a b b a b a a b
0 0 1 1 2 0 1 2 3 4 5
第一次停
a b a a b a
a b a a b b
此时 i = 5 j = 5,而 j != 1,所以 j = F[j - 1]= F[4]= 2
继续 i = 5 j = 2, 两者相等 .... 直到
第二次停
a b a a b b a b a a a
a b a a b b a b a a b
此时 i = 13, j = 10, j != 1,所以 j = F[j - 1]= F[9] = 4
还是不等, j = F[j - 1] = F[3] = 1,
相等,然后继续,而为什么每次都这样进行 更替呢,原因是 这样来进行前缀对称处后一个与 A 串对应处比较,然后不断缩小。
好比, a b a b c 与 a b c 进行匹配
a b c
0 0 0
a b
a b
a b a
a b c
此时 j = F[3] = 0
发现此时, j == 0,这已经是时 B串的首字母了,先判断是否相等,发现不相等,就将 A串进位了,因为A串此时位置以前的已经None了,然后 j == 0 与 i + 1 再开始循环
## 抛开这个例子,发现 B[1] != A[13],不得不继续降低, j = F[1] = 0(首字母处了)
然后发现相等,继续循环比较
a b a a b b a b a a b
a b a a b b a b a a b
发现相等,此时
输出的为 i - m = 24 - 10 = 14
j 再 归到 0 位置?,当然是可以利用前一部分再进行匹配的位置, 然后继续
完整版
package com.company;
import java.util.Arrays;
public class KMP {
public static int [] Next(String str)
{
int [] next = new int[str.length()];
// 将 str 转换成 字母数组
char B[] = str.toCharArray();
// 首先,默认第一个待匹配字母的 next 值为 0
next[0] = 0;
int j;
for (int i = 1; i < str.length(); i++)
{
// 每一个比较下标都是前一个数的 next 值
j = next[i - 1];
// System.out.println(j);
// 进行判断,如果 B[i] 与 B[j] 不等,且前面 next[i - 1] >= 1,即前一个字母有前缀匹配项时
// j = next[j]
// 直到 B[i] 与 B[j] 相等 或 匹配位置又回到了 待匹配字符串的开头(下面 j = j - 1,是因为 比较的第 j 个位置的不行,那么 相当于前置循环,又从for 开头的位置开始了,这等功效)
while (B[i] != B[j] && j >= 1)
j = next[j - 1];
// 前一个 while循环结果的判断
if (B[i] == B[j])
next[i] = j + 1;
else
next[i] = 0;
}
return next;
}
public static void match(String strA, String strB, int [] next)
{
char A[] = strA.toCharArray();
char B[] = strB.toCharArray();
int i = 0;
int j = 0;
while (i < A.length)
{
// 如果 A[i] = B[j]
if (A[i] == B[j])
{
i++;
j++;
// 如果 B字符串匹配完了一次
if (j == B.length)
{
// 输出完整匹配开头坐标在 A中的
System.out.println(i - B.length);
// 将 j 表示的坐标 回到 前一部分还可以用的位置 还比匹配 abcab 匹配的 abcab 那么 结束了之后 j 要回到 c 处,然后再与 i 比,而在 b 处的 next 值显而易见是等于 2 的,那么
j = next[j - 1];
}
}
else {
// 又回到了 待匹配字符串的开头了,回到原点, 下面进行 i++ 的原因是,如果 j==0 ,是会先进行上面的判断的,如果上面过不了,那么代表此时开头都不得匹配,只能再前进了
if (j == 0)
i++;
else
j = next[j - 1]; // 原因和上面 求 next 数组一样,既然不行,回到前缀处.
}
}
}
public static void main(String[] args) {
String str = "abaabbabaab";
System.out.println(Arrays.toString(Next(str)));
match("abaabaabbabaaabaabbabaabaabbabaab", str, Next(str));
}
}
原文链接:https://www.cnblogs.com/xmdykf/p/12509954.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- DES/3DES/AES 三种对称加密算法实现 2020-06-11
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-06-03
- 基础排序算法(附加java实现) 2020-06-02
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-05-29
- 最新美团面试技术四面拿offer:Spring、JVM、多线程、算法、 2020-05-21
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash