526互联

KMP算法

发布时间 2023-12-08 22:20:05作者: MGLblog

1.暴力匹配

暴力匹配算法的步骤如下：

  1. 遍历主串中的每个可能的起始位置，从第一个字符开始。
  2. 对于每个起始位置，逐个比较主串和模式串中对应位置的字符。
  3. 如果发现不匹配的字符，即主串和模式串中对应位置的字符不相等，将模式串向右移动一个位置，继续比较。
  4. 如果模式串完全匹配主串中的一段子串，即模式串的每个字符都与主串中的对应字符相等，则匹配成功，返回匹配的起始位置。
  5. 如果主串中的所有起始位置都比较完毕，仍然没有找到匹配的子串，则匹配失败，返回-1。
/**
 * @author 缪广亮
 * @version 1.0
 */
public class violenceMatch {
    public static void main(String[] args) {
        String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
        String str2 = "尚硅谷你尚硅你~";
        int index = violenceMatch(str1, str2);
        System.out.println("index=" + index);
    }

    //    暴力匹配算法实现
    public static int violenceMatch(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int s1Len = s1.length;
        int s2Len = s2.length;
        int i = 0;//i索引指向s1
        int j = 0;//j索引指向s2
        while (i < s1Len && j < s2Len) {//保证匹配时不越界
            if (s1[i] == s2[j]) {//匹配ok
                i++;
                j++;
            } else {//匹配失败
                i = i - (j - 1);
                j = 0;
            }
        }
//        判断如果匹配成功
        if (j == s2Len)
            return i - j;
        else
            return -1;
    }
}

2.KMP算法

很详尽的关于KMP算法的文章https://www.cnblogs.com/zzuuoo666/p/9028287.html

KMP算法的步骤如下：

  1. 预处理模式串，计算出部分匹配值（next数组）。
  2. 在主串中进行匹配，逐个比较主串和模式串中的字符。
  3. 如果发现不匹配的字符，即主串和模式串中对应位置的字符不相等，根据已经计算得到的部分匹配值来确定模式串的下一个比较位置。
  4. 根据部分匹配值，将模式串向右移动一定的位数，继续比较。
  5. 如果模式串完全匹配主串中的一段子串，即模式串的每个字符都与主串中的对应字符相等，则匹配成功，返回匹配的起始位置。
  6. 如果主串中的所有起始位置都比较完毕，仍然没有找到匹配的子串，则匹配失败，返回-1。

1.计算子串的部分匹配值表

//    获取到一个字符串（子串）的部分匹配值表
    public static int[] kmpNext(String dest) {
//        创建一个next数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0;//如果字符串是长度为1部分匹配值就是0
//        通过i和j两个指针来计算部分匹配值
        for (int i = 1, j = 0; i < dest.length(); i++) {
//            当dest.charAt(i)==dest.charAt(j),我们需要从next[j-1]获取新的j
//            直到我们发现有dest.charAt(i)==dest.charAt(j)成立才退出
//            kmp核心点
            while (j > 0 && dest.charAt(i) != dest.charAt(j))
                j = next[j - 1];
            if (dest.charAt(i) == dest.charAt(j))//满足时,部分匹配值就是+1
                j++;
            next[i] = j;
        }
        return next;
    }

2.kmpSearch

/**
     * @param str1 源字符串
     * @param str2 next 部分匹配表,是子串对应的部分匹配值
     * @return 如果是-1就是没有匹配到,否者返回第一个匹配的位置
     */
    public static int kmpSearch(String str1, String str2, int[] next) {
//        遍历源数组
        for (int i = 0, j = 0; i < str1.length(); i++) {
//            当str1.charAt(i)==str2.charAt(j),我们需要从next[j-1]获取新的j
//            直到我们发现有str1.charAt(i)==str2.charAt(j)成立才退出
//            kmp核心点
            while (j > 0 && str1.charAt(i) != str2.charAt(j))
                j = next[j - 1];
            if (str1.charAt(i) == str2.charAt(j))
                j++;
            if (j == str2.length())
                return i - (j - 1);
        }
        return -1;
    }

测试

public static void main(String[] args) {
    String str1 = "BBC ABCDAB ABCDABCDABDE";
    String str2 = "ABCDABD";
    int[] next = kmpNext(str2);
    System.out.println(Arrays.toString(next));
    int index=kmpSearch(str1,str2,next);
    System.out.println("index="+index);
}