当前位置：首页 > news >正文

数据结构-KMP算法

news 2025/8/26 8:48:33

先解决前缀与后缀串的最长匹配长度信息(前缀或后缀都不能取整体)。如下
位置6的前缀最长串就是abcab(不能取全部,即不能为abcabc)
位置6的后缀最长串就是bcabc(不能取全部,即不能为abcabc)

在这里插入图片描述


public class Code_KMP {public static void main(String[] args) {String s1 = "abcdefgjhi32jkls.dfs";String s2 = "s.df";System.out.println(getIndexOf(s1,s2));System.out.println(getIndexOf2(s1,s2));}public static int getIndexOf(String s1, String s2){if(s1 == null || s2 == null || s1.length() < 1 || s1.length() < s2.length()){return -1;}char[] str1 = s1.toCharArray();char[] str2 = s2.toCharArray();int x = 0;int y = 0;int[] next = getNextArray(str2);while(x < str1.length && y<str2.length){if(str1[x] == str2[y]){x++;y++;}else if(next[y] == -1){x++;}else{y = next[y];}}return y == str2.length ? x - y : -1;}public static int[] getNextArray(char[] match){if(match.length == 1){return new int[]{-1};}int[] nextArray = new int[match.length];nextArray[0] = -1;nextArray[1] = 0;nextArray[2] = (match[0] == match[1] ? 1 : 0);for (int i = 3; i < match.length; i++) {int cn = nextArray[i-1];while(cn != -1 && match[cn] != match[i-1]){cn = nextArray[cn];}nextArray[i] = cn + 1;}return nextArray;}public static int getIndexOf2(String s1, String s2){if(s1 == null || s2 == null || s1.length() < 1 || s1.length() < s2.length()){return -1;}char[] str1 = s1.toCharArray();char[] str2 = s2.toCharArray();int x = 0;int y = 0;int[] next = getNextArray2(str2);while(x < str1.length && y<str2.length){if(str1[x] == str2[y]){x++;y++;}else if(next[y] == -1){x++;}else{y = next[y];}}return y == str2.length ? x - y : -1;}public static int[] getNextArray2(char[] match){if(match.length == 1){return new int[]{-1};}int[] nextArray = new int[match.length];nextArray[0] = -1;nextArray[1] = 0;int cn = 0;int i = 2;while(i <match.length){if(match[0] == match[i]){ // 匹配成功nextArray[i++] = ++cn;}else if(cn > 0){cn = nextArray[cn];}else{nextArray[i++] = 0;}}return nextArray;}
}