KMP算法

2020-03-17 16:05:00来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Java Web

下一篇:SpringBoot引入第三方jar包或本地jar包的处理方式