KMP java实现【算法】

谁借莪１个温暖的怀抱￠ 2022-05-13 03:40 164阅读 0赞

package com.using.test;
    
    import org.junit.Test;
    
    public class KMPTest { 
    
        @Test
        public  void test() {
            //Arrays.stream(getNext("ababab")).forEach(System.out::println);
            String target = "ABABCABCACBAB";
            String target1 = "abbababaaababaa";
            String[] child = {
       "ABCAC", "ABABAB", "ABABABB"};
            String[] child1 = {
       "ababaaababaa"};
            for (String t : child) {
                System.out.println(target + " - " + t + ":" + compareKMP(target, t, getNext(t)));
            }
        }
    
        /** * 测试用例： * 主串： ABABCABCACBAB * 模式串：ABCAC 5 * 模式串：ABABAB -1 * 模式串：ABABABB -1 * 主串： abbababaaababaa * 模式串：ababaaababaa 3 * */
        private static int compareKMP(String str1, String str2, int[] next){
            int i = 0;
            int j = 0;
            char[] chars1 = str1.toCharArray();
            char[] chars2 = str2.toCharArray();
            while (i < chars1.length && j < chars2.length){
                if (chars1[i] == chars2[j]){
                    i ++;
                    j ++;
                }else if (j>0){
                    j = next[j];
                }else{
                    i ++;
                }
            }
            return j == chars2.length ? i-j : -1;
        }
    
        private static int[] getNext(String str){
            char[] chars = str.toCharArray();
            if (chars.length == 1){
                return new int[]{-1};
            }
            int[] next = new int[chars.length];
            next[0] = -1;
            next[1] = 0;
            int cn = 0;
            int i = 2;
            while(i < chars.length){
                if (chars[cn] == chars[i-1]){
                    next[i++] = ++cn;
                }else if(cn > 0){
                    cn = next[cn];
                }else{
                    next[i++] = 0;
                }
            }
            return next;
        }
    }