Java字符串匹配算法 KMP算法与暴力匹配的比较

Bertha 。 2021-10-24 00:24 284阅读 0赞

## 首先看一下暴力匹配代码 ##

--------------------

package 暴力匹配;
    
    public class BaoLiMatches {
        public static void main (String[] args) {
            String str1 = "abcdefghigkm";
            String str2 = "gkm";
            int num = matches(str1, str2);
            System.out.println(num);//输出9为正确;
        }
    
        public static  int matches (String str1, String str2) {
            char[] s1 = str1.toCharArray();
            char[] s2 = str2.toCharArray();
            int len1= s1.length;
            int len2= s2.length;
            int i=0;//str1索引
            int j=0;//str2索引
            while (i < len1 && j < len2) {
                if (s1[i] == s2[j]) {
                    i++;
                    j++;
                }else{
                    i=i-j+1;
                    j=0;
                }
            }
            if (j==len2){
                return i-j;
            }else {
                return -1;
            }
        }
    }

## kmp算法: ##

## 代码: ##

--------------------

package kmp算法;
    
    public class kmpMatches {
        public static void main (String[] args) {
            String str1 = "12312346aaab";
            String str2 = "aaab";
            int i = kmpMatchs(str1, str2, kmpNext(str2));
            System.out.println("匹配位置为" + i);
    
        }
    
        private static int kmpMatchs (String str1, String str2, int[] next) {
            for (int i = 0, j = 0; i < str1.length(); i++) {
                while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                    j = next[j - 1];
                }
                if (str1.charAt(i) == str2.charAt(j)) {
                    j++;
                }
                if (j == str2.length()) {
                    return i - j + 1;
                }
    
            }
            return -1;
        }
    
        private static int[] kmpNext (String str) {
            int[] next = new int[str.length()];
            next[0] = 0;
            for (int i = 1, j = 0; i < str.length(); i++) {
                while (j > 0 && str.charAt(i) != str.charAt(j)) {
                    j = next[j - 1];
                }
                if (str.charAt(i) == str.charAt(j)) {
                    j++;
                }
                next[i] = j;
            }
            return next;
    
        }
    }

相信到这里小伙伴都看懂了吧,加油哦!!!