# KMP algorithm O(M+N)

• I use the KMP algorithm instead the brute-force, so the time complexity is O(M+N) instead of O(MN), but it seems like it take more time for a smaller input size

code is below:

`````` public int strStr(String source, String pattern) {

int[] pttn = this.next(pattern);

if (pttn == null || source == null || source.length() == 0
|| source.length() < pattern.length()) {
return -1;
}

int sn = source.length();
int pn = pattern.length();
int i = 0;
int j = 0;
while (i+j <sn) {

if (source.charAt(i+j) == pattern.charAt(j)) {
if (j == pn - 1)
return i;
j++;
} else {
if (j != 0) {
// find the initial i
i = i + j - pttn[j - 1];
j = 0;
} else {
i++;
j = 0;
}
}

}

return -1;

}

private int[] next(String pattern) {

if (pattern == null || pattern.length() == 0) {
return null;
}

int len = pattern.length();
int[] result = new int[len]; // 建立匹配表
result[0] = 0;

int i = 1; // pattern 指针
int j = 0; // 最大匹配长度， pattern 上的最大匹配长度

while (i < len) {

if (pattern.charAt(j) == pattern.charAt(i)) {
// 如果匹配 则 j+1， 然后assign给相对应的匹配表
j++;
result[i] = j;
i++;
} else {
// 如果不匹配-则j 开始回退

if (j != 0) {
// 当j不为0时， j 退1(前一位 和 i-1 时候 有匹配)， 查表找出对应的匹配表值， j 退到当前位置
j = result[j - 1];
} else {
// 当j为0时， 说明已经没有任何值与 pattern[i] 匹配， 所以匹配长度应该为0， i++
// 开始进行下一轮匹配
result[i] = j;
i++;
}

}

}

System.out.println(Arrays.toString(result));
return result;

}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.