KMP算法
str1 str2 求str2在str1中的開始位置
幾個(gè)概念：
1.最長前綴和最長后綴的匹配長度
2.依據(jù)概念1暑始，求出str2中每個(gè)元素的最長前綴和最長后綴匹配長度，得出數(shù)組next
3.利用next,開始對暴力算法進(jìn)行加速婴削，從而得到KMP算法廊镜。
下面講next數(shù)組怎么得到。
1.向前找唉俗。
package basic_class_02;
public class Code_01_KMP {
public static int getIndexOf(String s, String m) {
if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
}
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
int si = 0;
int mi = 0;
int[] next = getNextArray(ms);
while (si < ss.length && mi < ms.length) {
if (ss[si] == ms[mi]) {
si++;
mi++;
} else if (next[mi] == -1) {
si++;
} else {
mi = next[mi];
}
}
return mi == ms.length ? si - mi : -1;
}
public static int[] getNextArray(char[] ms) {
if (ms.length == 1) {
return new int[] { -1 };
}
int[] next = new int[ms.length];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while (pos < next.length) {
if (ms[pos - 1] == ms[cn]) {
next[pos++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[pos++] = 0;
}
}
return next;
}
public static void main(String[] args) {
String str = "abcabcababaccc";
String match = "ababa";
System.out.println(getIndexOf(str, match));
}
}
KMP算法擴(kuò)展題目指一：
題目：
給定一個(gè)字符串str1嗤朴， 只能往str1的后面添加字符變成str2。
要求1： str2必須包含兩個(gè)str1虫溜， 兩個(gè)str1可以有重合雹姊， 但是不
能以同一個(gè)位置開頭。
要求2： str2盡量短
最終返回str2
舉例：
str1 = 123吼渡， str2 = 123123 時(shí)容为， 包含兩個(gè)str1， 且不以相同
位置開頭寺酪， 且str2最短坎背。
str1 = 123123， str2 = 123123123 時(shí)寄雀， 包含兩個(gè)str1得滤， 且不
以相同位置開頭， 且str2最短盒犹。
str1 = 111懂更， str2 = 1111 時(shí)， 包含兩個(gè)str1急膀， 且不以相同位
置開頭沮协， 且str2最短。
package basic_class_02;
public class Code_02_KMP_ShortestHaveTwice {
public static String answer(String str) {
if (str == null || str.length() == 0) {
return "";
}
char[] chas = str.toCharArray();
if (chas.length == 1) {
return str + str;
}
if (chas.length == 2) {
return chas[0] == chas[1] ? (str + String.valueOf(chas[0])) : (str + str);
}
int endNext = endNextLength(chas);
return str + str.substring(endNext);
}
public static int endNextLength(char[] chas) {
int[] next = new int[chas.length + 1];
next[0] = -1;
next[1] = 0;
int pos = 2;
int cn = 0;
while (pos < next.length) {
if (chas[pos - 1] == chas[cn]) {
next[pos++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[pos++] = 0;
}
}
return next[next.length - 1];
}
public static void main(String[] args) {
String test1 = "a";
System.out.println(answer(test1));
String test2 = "aa";
System.out.println(answer(test2));
String test3 = "ab";
System.out.println(answer(test3));
String test4 = "abcdabcd";
System.out.println(answer(test4));
String test5 = "abracadabra";
System.out.println(answer(test5));
}
}
給定兩個(gè)二叉樹T1和T2卓嫂， 返回T1的某個(gè)子樹結(jié)構(gòu)是否與T2的結(jié)構(gòu)相等
package basic_class_02;
public class Code_03_KMP_T1SubtreeEqualsT2 {
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value = data;
}
}
public static boolean isSubtree(Node t1, Node t2) {
String t1Str = serialByPre(t1);
String t2Str = serialByPre(t2);
return getIndexOf(t1Str, t2Str) != -1;
}
public static String serialByPre(Node head) {
if (head == null) {
return "#!";
}
String res = head.value + "!";
res += serialByPre(head.left);
res += serialByPre(head.right);
return res;
}
// KMP
public static int getIndexOf(String s, String m) {
if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
}
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
int[] nextArr = getNextArray(ms);
int index = 0;
int mi = 0;
while (index < ss.length && mi < ms.length) {
if (ss[index] == ms[mi]) {
index++;
mi++;
} else if (nextArr[mi] == -1) {
index++;
} else {
mi = nextArr[mi];
}
}
return mi == ms.length ? index - mi : -1;
}
public static int[] getNextArray(char[] ms) {
if (ms.length == 1) {
return new int[] { -1 };
}
int[] nextArr = new int[ms.length];
nextArr[0] = -1;
nextArr[1] = 0;
int pos = 2;
int cn = 0;
while (pos < nextArr.length) {
if (ms[pos - 1] == ms[cn]) {
nextArr[pos++] = ++cn;
} else if (cn > 0) {
cn = nextArr[cn];
} else {
nextArr[pos++] = 0;
}
}
return nextArr;
}
public static void main(String[] args) {
Node t1 = new Node(1);
t1.left = new Node(2);
t1.right = new Node(3);
t1.left.left = new Node(4);
t1.left.right = new Node(5);
t1.right.left = new Node(6);
t1.right.right = new Node(7);
t1.left.left.right = new Node(8);
t1.left.right.left = new Node(9);
Node t2 = new Node(2);
t2.left = new Node(4);
t2.left.right = new Node(8);
t2.right = new Node(5);
t2.right.left = new Node(9);
System.out.println(isSubtree(t1, t2));
}
}
