assumptions

String str1 and str2, whether str1 contains str2, and if so, return str2 at the beginning of str1. For example, str1:ABC1234de str2:1234de str1 contains str2.

The classical approach is to iterate over STR1 and STR2 in order to compare them. The worst case example is str1:11111111112(length N) str2:1112(length M), then the time complexity is O(N * M).

How do you optimize? Implementation time is O(N)

KMP algorithm

Str2 prefix and suffix

Before implementing THE KMP algorithm, we first need to know the maximum length of str2 prefix and suffix equal, as an auxiliary array, and this array plays a key role in the KMP algorithm. Remember for the next [I].

Next [I]: next[0] = -1; next[0] : next[0] = -1; next[1] = 0;

For example, aabaabs next[0] = -1; next[1] = 0; next[2] = 1; next[3] = 0; next[4] = 1; next[5] = 2; next[6] = 3;

So how do I find the next[I] array of STR2?

We evaluate next[I] using the value of next[I – 1]. Refer to the following figure:

///////////////////////////////////////////////////////////////////////////////////////////////

We can use the code to understand:

Public static int[] getNextArray(char[] ms) {next[0] = -1; if (ms.length == 1) { return new int[]{-1}; } int[] next = new int[ms.length]; next[0] = -1; next[1] = 0; // Next [0] and next[1] are predetermined, so I starts from 2 int I = 2; Next [i-1] = 0, cn = 0; next[i-1] = 0; int cn = 0; If (ms[i-1] == ms[cn]) {// If (ms[i-1] == ms[cn]) {// Next [I] = (cn+1); Next [(I +1)] // Next [(I +1)] = (ms[(cn+1)]) next[I ++] = +cn; } else if (cn > 0) {// if (cn > 0) {ms[next[cn]] cn = next[cn]; Next [i++] = 0;} next[i++] = 0; next[i++] = 0; } } return next; }Copy the code

The realization of KMP algorithm

Once we have the Next array, we can use it for comparison.

Refer to the following figure:

///////////////////////////////////////////////////////////////////////////////////////////////

We can use the code to understand:

public static int KMP(String s,String m){ if (s == null || m == null || m.length() < 1 || s.length() < m.length()){ return -1; } char[] str1 = s.toCharArray(); char[] str2 = m.toCharArray(); //str1 cursor int i1 = 0; //str2 cursor int i2 = 0; Int [] next = getNextArray(str2); If (str1[i1] == str2[i2]){i1++; if (str1[i1] == str2[i2]){i1++; i2++; }else if(next[i2] == -1){i2 == 0; So we're at the beginning. // At the beginning of the comparison is not equal, only Str1 cursor moved back i1++; }else {i2 = next[i2]; i2 = next[i2]; Return i2 == str2.length? i1 - i2 : -1; }Copy the code

The overall code

Public static int[] getNextArray(char[] ms) {next[0] = -1; if (ms.length == 1) { return new int[]{-1}; } int[] next = new int[ms.length]; next[0] = -1; next[1] = 0; // Next [0] and next[1] are predetermined, so I starts from 2 int I = 2; Next [i-1] = 0, cn = 0; next[i-1] = 0; int cn = 0; If (ms[i-1] == ms[cn]) {// If (ms[i-1] == ms[cn]) {// Next [I] = (cn+1); Next [(I +1)] // Next [(I +1)] = (ms[(cn+1)]) next[I ++] = +cn; } else if (cn > 0) {// if (cn > 0) {ms[next[cn]] cn = next[cn]; Next [i++] = 0;} next[i++] = 0; next[i++] = 0; } } return next; } public static int KMP(String s,String m){ if (s == null || m == null || m.length() < 1 || s.length() < m.length()){ return -1; } char[] str1 = s.toCharArray(); char[] str2 = m.toCharArray(); //str1 cursor int i1 = 0; //str2 cursor int i2 = 0; Int [] next = getNextArray(str2); If (str1[i1] == str2[i2]){i1++; if (str1[i1] == str2[i2]){i1++; i2++; }else if(next[i2] == -1){i2 == 0; So we're at the beginning. // At the beginning of the comparison is not equal, only Str1 cursor moved back i1++; }else {i2 = next[i2]; i2 = next[i2]; Return i2 == str2.length? i1 - i2 : -1; } public static void main(String[] args) { String str1 = "abcabcababaccc"; String str2 = "ababa"; System.out.println(KMP(str1, str2)); }Copy the code