java实现字符串的一般和KMP模式匹配算法

r囧r小猫 2022-06-10 13:25 59阅读 0赞

/**
     * Created by on 2017/8/20.
     */
    public class StringIndex {
        public static void main(String agrs[]){
            String s = "dsadaaaabdad";
            String t = "aaaab";
    //        int pos = BFIndex(s,t);
            int pos = KMP(s,t);
            System.out.println(pos);
    
            int[] next = new int[t.length()];
            get_next(t,next);
            for (int i = 0; i < next.length; i++) {
                System.out.print(next[i]+" ");
            }
        }
    
        /**
         * 字符串的一般模式匹配算法
         * @param s 主串
         * @param t 子串
         * @return 子串在主串的下标
         * 时间复杂度：O(n+m) 最坏O(n*m)
         */
        public static int BFIndex(String s,String t){
            int i = 0,j = 0;
            while (i < s.length() && j < t.length()){
                if (s.charAt(i) == t.charAt(j)){
                    i++;
                    j++;
                }else {
                    i = i - j + 1;
                    j = 0;
                }
            }
            if (j >= t.length()){
                return i - t.length();
            }else {
                return -1;
            }
        }
    
        public static int KMP(String s,String t){
            int i = 0,j = 0;
            int next[] = new int[t.length()];
            //获得next数组
            get_nextval(t,next);
            //开始匹配
            while (i < s.length() && j < t.length()){
                if (j == 0 || s.charAt(i) == t.charAt(j)){
                    //相等就继续
                    i++;
                    j++;
                }else {
                    //否则主串位置不变，子串位置 j = next[j]
                    j = next[j];
                }
            }
            if (j >= t.length()){
                //子串匹配完返回子串所在主串下标
                return i - t.length();
            }else {
                return -1;
            }
        }
    
        /**
         * 求解KMP算法的next数组
         * 前两位必为0，1。
         * 后面根据前一位进行比较得到：
         *next[j]前一位与其next[j]值对应的内容进行比较，如果相等，next[j+1] = next[j]+1（在java中需要-1 = next[j]+0）；
         * 如果不等，继续向前寻找next[j-1]值对应的内容来与前一位nex[j-1]进行比较，依次比较[j-2...]和它值对应的内容，直到相等。
         * 如果到第一位都不相等则next[j+1]=1(在java中需要-1 = 0)。其中j为下标
         *
         * @param next
         */
        public static void get_next(String t , int next[]){
            int i = 0,j = -1;
            next[0] = -1; //java中第一位为-1
            while (i < t.length()-1){
                if (j == -1){ //如果到第一位都不相等则next[j+1]=0
                    next[++i] = 0;
                    j = 0;
                }
                if (t.charAt(i) == t.charAt(j)){
                    //确定next[i+1] next[i+1] = next[i] + 1
                    //因为前面j = next[j] = next[i],++j = next[i] + 1 = next[++i] = next[i+1]
                    next[++i] = ++j;
                }else {
                    j = next[j];//向前寻找下一位next
                }
            }
    
        }
    
        public static void get_nextval(String t,int nextval[]){
            int i = 0,j = -1;
            nextval[0] = -1;
            while (i < t.length()-1){
                if (j == -1){ //如果到第一位都不相等则next[j+1]=0
                    nextval[++i] = 0;
                    j = 0;
                }
                if (t.charAt(i) == t.charAt(j)){
                    i++;
                    j++;
                    if (t.charAt(i) == t.charAt(j)){
                        //如果匹配的一个位置的下一位位置也匹配，则next[i+1]与当前next[i]相等
                        nextval[i] = nextval[j];//相当于nextval[i+1] = nextval[i]
                    }else {
                        nextval[i] = j;
                    }
    
                }else {
                    j = nextval[j];
                }
            }
        }
    }