KMP算法的java实现

• Z时代
• 2024-01-10
• 分类：综合

package com.trs.utils;
public class KMPStr {
    /*
     * 在KMP算法中，最难求的就是next函数，如何理解next函数是一个难题，特别是k=next[k]，这里
     * 需要指出的是当p[i]!=p[j]时，我们只有通过回溯将k的值逐渐减小，貌似类似与用到了动态规划的思想 参考网上阮一峰老师的博客讲解的十分详细
     */
    private static int[] getNext(String t) {
        int[] next = new int[t.length()];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < t.length() - 1) {
            if (k == -1 || t.charAt(j) == t.charAt(k)) {
                j++;
                k++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        for (int i : next) {
            System.out.print(i + ":");
        }
        System.out.println();
        return next;
    }
    public static int kmpStrIndex(String s, String t, int[] next) {
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                // i不变，j后退
                j = next[j];
            }
            if (j == t.length()) {
                return i - j;
            }
        }
        return -1;
    }
}

View Code

以上是 KMP算法的java实现 的全部内容， 来源链接： utcz.com/z/389573.html