Given a Haystack string and a Needle string, find the first position (starting from 0) where the Needle string appears in the Haystack string. If none exists, -1 is returned.

Example 1:

Enter: haystack ="hello", needle = "ll"Output: 2Copy the code

Example 2:

Enter: haystack ="aaaaa", needle = "bba"Output: 1Copy the code

Idea 1: Violent matching

Suppose haystack=”abcabcx”, needle=”abcabx”, m is the length of haystack, n is the length of needle, I is the index of string haystack, j is the index of string needle, Comparison of Haystack [I] and Needle [J], as shown in the figure below:

Go back to the two Pointers and re-compare until needle matches perfectly or haystack string loops end without matching, as shown below.

The violent matching method requires continuous backtracking of two Pointers, and the time complexity is O(m*n).

Idea 2: KMP algorithm

Let’s take a look at the first mismatch above, and make the colors clear:

The ab(green) before the mismatch character is known to match, just as the first two characters of the needle are ab(red),

This suggests that we can try to reduce the number of matches by making red ab equal to green AB. We can move j directly to the next character of red AB, and I remains unchanged to continue matching, as shown below:

Continue matching, and if you encounter any more mismatches, repeat the above steps until the Needle is a perfect match, or the Haystack string loop ends without a match, as shown below:

This saves a lot of efficiency by not backtracking I.

Implement the above steps in code:

var strStr = function(haystack, needle) {
    var m = haystack.length, n = needle.length;
    if(! n)return 0;
    var next = kmpProcess(needle);
    for(var i = 0, j = 0; i < m;) {
        if(haystack [I] = = needle [j]) {/ / character match, I and j are step forward i++, j++; }if(j == n) returni - j; // Needle is fully matched, return to the matching positionif(haystack[i] ! = needle[j])if(j > 0) {// how TODO reset j? }else{ i++; }}}return- 1; };Copy the code

So if characters don’t match, how do you tell your program to know where to reset j? Let’s take a look at the first mismatch:

The string “ab” is of length 2. Reset j to needle array with subscript 2 (array subscript starts at 0). We can use this idea to record the position of j reset for each mismatched character in needle into an array next. What we need to do is find the array next.

Next, let’s evaluate the Next array. The worst-case scenario is that j is reset to zero, and the array is filled with zeros first.

Suppose x is the index traversing the Needle and y is the index starting at 0 of the neddle array, which is where J will reset (that is, the value stored into the next array). Because needle has no prefix or suffix on its first character, next[0] is always 0, so x starts at 1. Next is computed as follows:

  1. needle[x] ! Neddle [y] = neddle[y], y=0, next[x]=0, and x step forward, as shown below:

2.needle[x] ! Neddle [y] = neddle[y], y=0, next[x]=0, and x step forward, as shown below:

  1. Needle [x] == neddle[y], as shown below:

    Next [x]= y(now 1) and x (now 1). Next [x]= next[3]=1:

  2. Needle [x] == neddle[y], as shown below:

    Next [x]= y(now 2) and x (now 2). Next [x]= next[4]=2:

5.needle[x] ! = neddle[y], because y! If needle[x] =0, we need to move y to next[y-1], that is, y=0, then compare needle[x] with neddle[y]. =0 or needle[x]! = neddle[y] when x cannot advance, to stay in place, as shown below:

The next array is [0, 0, 0, 1, 2, 0].

Implement the above two steps in code:

var strStr = function(haystack, needle) {
    var m = haystack.length, n = needle.length;
    if(! n)return 0;
    var next = kmpProcess(needle);
    for(var i = 0, j = 0; i < m;) {
        if(haystack [I] = = needle [j]) {/ / character match, I and j are step forward i++, j++; }if(j == n) returni - j; // Needle is fully matched, return to the matching positionif(haystack[i] ! = needle[j])if(j > 0) { j = next[j - 1]; // reset j}else{ i++; }}}return- 1; }; var kmpProcess =function(needle) {
    var y = 0;
    var x = 1;
    var next = new Array(needle.length).fill(0);
    while (x < needle.length) {
        if (needle[x] == needle[y]) {
            y++;
            next[x] = y;
            x++;
        } else if (y > 0) {
            y = next[y - 1];
        } else{ next[x] = 0; x++; }}return next;
}

console.log(strStr('abcabcabya'.'abcaby')); / / 3Copy the code

The time complexity of kmpProcess is O(n), there is no need to backtrace index I of Haystack, and the time complexity of the whole algorithm is O(m+ N).