超級實習生學習打卡第6天——Java實作KMP算法比對字元串的子串

Java實作KMP算法比對字元串的子串

public class KMP {
    public static void main(String[] args) throws IOException {
        String s = "abc";
        String s1 = " jhjkhdjabclshgfksdf";
        System.out.println("是否比對到子串：" + searchStr(s1, s)); 

    }
    public static boolean searchStr(String s1, String s2) {
        //KMP算法
        int[] next = getNext(s2); //擷取next數組
        int i = 0;  //i表示s1的下标
        int j = 0;  //j表示s2的下标
        while (i < s1.length() && j < s2.length()) { //當i小于s1的長度且j小于s2的長度時
            if (j == -1 || s1.charAt(i) == s2.charAt(j)) { //當j小于0或者s1的第i個字元與s2的第j個字元相等時
                i++; //i加1
                j++; //j加1
            } else { //當j大于0且s1的第i個字元與s2的第j個字元不相等時
                j = next[j]; //j等于next數組的第j個元素值
            }
        }
        if (j == s2.length()) { //當j等于s2的長度時
            return true; //傳回true
        }
        return false;  //否則傳回false
    }

    public static int[] getNext(String s) {
        //KMP擷取Next
        int[] next = new int[s.length()]; //next數組
        next[0] = -1; //next數組的第一個元素值為-1
        int k = -1; //k表示目前字元串的字首
        int j = 0; //j表示目前字元串的字尾
        while (j < s.length() - 1) { //當j小于字元串長度-1時
            if (k == -1 || s.charAt(j) == s.charAt(k)) { //當k小于0或者目前字元與字首字元相等時
                k++; //k加1
                j++; //j加1
                if (s.charAt(j) != s.charAt(k)) { //當目前字元與字尾字元不相等時
                    next[j] = k; //next數組的第j個元素值為k
                } else { //當目前字元與字尾字元相等時
                    next[j] = next[k]; //next數組的第j個元素值為next數組的第k個元素值
                }
            }
            else { //當k大于0且目前字元與字首字元不相等時
                k = next[k]; //k等于next數組的第k個元素值
            }
        }
        return next;
    }
}