KMP算法

KMP算法?
【题目】?
给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有字串match，则返回match在str中的开始位置，不含有则返回-1。?
【举例】?
str=“acbc”，match=“bc”。返回2。?
str=“acbc”，match=“bcc”。返回-1。?
【要求】?
? ?public 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 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;?
????}