在字符串text中查找子串pattern（KMP算法）

迷南。 2021-09-26 14:52 357阅读 0赞

/** * @author zfr * @date 2018-4-7 * kmp算法完成的任务是：给定两个字符串text和pattern， * 长度分别为n和m，判断pattern是否在text中出现，如果出现则返回出现的位置。 * 否则返回-1 * 常规方法是遍历text的每一个位置，然后从该位置开始和pattern进行匹配，但是这种方法的复杂度是O(n*m)。 * kmp算法通过一个O(m)的预处理，构造数组next，使匹配的复杂度降为O(n+m)。 */
    public class KMPSubString { 
    
    
        /** * @param args */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            String text = "111.wwaabb.w.wwwaabbabcdefaa";
            String pattern = "aabbabcdefaa";
            int index = indexOf(text,pattern);
            System.out.println(index);
        }
        /* * 返回第一个匹配的索引位置，如果不匹配，则返回-1 */
        private static int indexOf(String text, String pattern) {
            // TODO Auto-generated method stub
            //若text长度小于pattern，则text一定不包含pattern
            if(text == null || pattern==null||pattern.length()==0||text.length()<pattern.length())
                return -1;
            int[] next = generateNext(pattern);//产生Next数组
            char[] ch_text = text.toCharArray();
            char[] ch_pattern = pattern.toCharArray();
            int j = 0;
            int i = 0;
            for (; i < ch_text.length&&j<ch_pattern.length; ) {
                if(ch_text[i]==ch_pattern[j]){
                    i++;
                    j++;
                }else{
                    if(j!=0){
                        j = next[j-1];
                    }else{
                        i++;
                    }
                }
            }
            if(j==pattern.length()){
                return i - j;
            }
            return -1;
        }
        /* * next 数组的求法 * next 数组next[i]表示的字符串前缀和后缀的最长公共部分 */
        private static int[] generateNext(String pattern) {
            // TODO Auto-generated method stub
            int[] next = new int[pattern.length()];
            char[] ch = pattern.toCharArray();
            int j = 0;
            for (int i = 1; i < ch.length;) {
                if(ch[i]==ch[j]){
       //如果相等，则next[i] = j+1
                    next[i]=j+1;
                    i++;
                    j++;
                }else{
       //否则，判断j是否等于0，等于0则直接设置next[i]=0,否则j取next[j-1]的值
                    if(j != 0){
                        j = next[j-1];
                    }else{
                        next[i] =0;
                        i++;
                    }
                }
            }
            System.out.println("打印next数组:");
            for (int i = 0; i < next.length; i++) {
                System.out.print(next[i]+" ");
            }
            System.out.println();
            return next;
        }
    
    
    }