java kmp算法

KMP算法是一种改进的字符串模式匹配算法，可以在O(n m)的时间复杂度以内完成字符串的匹配操作。它的核心思想是利用已经得到的“部分匹配”，将模式串尽可能多地向右“滑动”一段距离，然后继续比较。 = -1;
int i = 0, j = -1;
while (i < p.length() - 1) {
if (j == -1 || p.charAt(i) == p.charAt(j)) {
i++;
j++;
next[i = j;
} else {
j = next[j];
}
}
return next;
}

以上就是KMP算法的Java实现。通过使用这个算法，可以在字符串匹配过程中提高效率。

相关问题

javakmp算法实现

KMP算法是一种改进的字符串匹配算法，它的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。在Java中，可以通过以下代码实现KMP算法：

public class KMP {
    public static int KMP(String Str, String Sub, int pos){
        if (Str == null || Sub == null){
            return -1;
        }
        if (pos >= Str.length() || pos < 0){
            return -1;
        }
        int i = pos;
        int j = 0;
        int[] next = new int[Sub.length()];
        getNext(next, Sub);
        while(i < Str.length() && j < Sub.length()){
            if (j == -1 || Str.charAt(i) == Sub.charAt(j)){
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j >= Sub.length()){
            return i - j;
        } else {
            return -1;
        }
    }
    
    public static void getNext(int[] next, String sub){
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int k = 0;
        while(i < next.length){
            if (k == -1 || sub.charAt(k) == sub.charAt(i-1)){
                next[i] = k + 1;
                i++;
                k++;
            } else {
                k = next[k];
            }
        }
    }
}

javakmp算法的实现

KMP算法的实现是通过计算模式串的next数组，然后在主串中进行匹配。在Java中，可以按照以下步骤实现KMP算法：

1. 首先，定义一个函数来计算模式串的next数组，即模式串T中每一个长度为j (0 < j < T.length) 的前缀所对应的next[j]的值。这个函数可以按照以下步骤进行计算：
- 初始化一个长度为T.length的next数组，并将其所有元素初始化为0。
- 使用两个指针i和j，分别指向模式串的第一个字符和第二个字符。
- 循环遍历模式串的字符：
- 如果T[i]等于T[j]，则将next[j+1]的值设置为j+1，并将i和j都加1。
- 如果T[i]不等于T[j]，则判断j的值：
- 如果j等于0，则将next[j+1]的值设置为0，并将i加1。
- 如果j不等于0，则将j更新为next[j]的值。

2. 定义一个函数来进行匹配，接收一个主串S和一个模式串T作为参数。这个函数可以按照以下步骤进行匹配：
- 使用两个指针i和j，分别指向主串和模式串的第一个字符。
- 循环遍历主串的字符：
- 如果S[i]等于T[j]，则将i和j都加1。
- 如果S[i]不等于T[j]，则判断j的值：
- 如果j等于0，则将i加1。
- 如果j不等于0，则将j更新为next[j]的值。

3. 在匹配过程中，如果j的值等于模式串的长度，则说明匹配成功，返回主串中匹配的起始位置。

下面是KMP算法的Java实现代码：

public class KMP {
    public int kmpMatch(String S, String T) {
        char[] sArr = S.toCharArray();
        char[] tArr = T.toCharArray();
        
        int[] next = getNext(T);
        
        int i = 0, j = 0;
        while (i < sArr.length && j < tArr.length) {
            if (sArr[i] == tArr[j]) {
                i++;
                j++;
            } else if (j == 0) {
                i++;
            } else {
                j = next[j];
            }
        }
        
        if (j == tArr.length) {
            return i - j;
        } else {
            return -1;
        }
    }
    
    private int[] getNext(String T) {
        char[] tArr = T.toCharArray();
        int[] next = new int[tArr.length];
        
        int i = 0, j = -1;
        next[0] = -1;
        
        while (i < tArr.length - 1) {
            if (j == -1 || tArr[i] == tArr[j]) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        
        return next;
    }
}