This is the 25th day of my participation in Gwen Challenge

preface

StrStr () is implemented as follows:

Implement the strStr() function.

Given two strings haystack and needle, find the first place in the haystack string where needle appears (the subscript starts at 0). If none exists, -1 is returned.

Description:

What value should we return when needle is an empty string? This is a good question to ask in an interview.

For this case, we should return 0 when needle is an empty string. This is consistent with the C language STRSTR () and the Java definition of indexOf().

Example 1:

Input: haystack = “hello”, needle = “ll” Output: 2

Example 2:

Input: haystack = “aaAAA “, needle = “bba” Output: -1

Example 3:

Input: haystack = “”, needle = “” Output: 0

A, thinking

STR: original string target: target string

Implement the Java String Api indexOf manually to find the position of needle in String STR. If target is empty, return 0.

Manual implementation, manual implementation, manual implementation! For the third time, do not use Java native apis.

There are two ways to solve this problem:

1. Double cycle Violence Matching (Scheme 1)
2. KMP algorithm (commonly known as porn watching algorithm)

The first loop iterates through STR to select the starting element, and the second loop selects the string with the length of target.length to determine whether it is equal to target, and returns the corresponding result if it is equal.

Graphic KMP algorithm

STR = ABCABCABF, target = ABCABF

To be honest, I still don’t know how to build the partial matching table. I will fill in the holes when I figure it out later.

KMP I think Ruan Yifeng, this article is written very good, recommend.

The core idea of KMP algorithm is to build a partial matching table and move to the next position when it encounters unmatched elements. (See below for detailed steps)

The first step is to build a partial match table

The partial matching table of ABCABF is as follows:

The values in the partial match table next represent: For example, next[4] (4 is the subscript for the fifth element), which represents the length of the common element with the longest prefix and suffix in ABCAB, whose prefixes are A, AB, ABC, ABCA, The suffixes are BCAB, CAB, AB, B, and apparently the longest common element is AB, i.e., next[4] = 2

Formula for moving: Move digit = number of matched characters – corresponding partial matching value (that is, move the entire character to the next matching position)

Characters are not equal for the first time

For the first time, F! = A, the matched character is ABCAB with A length of 5, and the partial matching value of ABCAB is 2, so the moved position is 5-2 = 3, as shown in the following figure:

The second time, C! = A, the matched character AB is 2 in length, and the partial matching value of AB is 0, so the moved position is 2-0 = 2, as shown below:

Bitwise comparison, find the same, return the result subscript 5 can be. As shown below:

Second, the implementation

Exhaustive method

The implementation code

    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if(haystack.charAt(i + j) ! = needle.charAt(j)) { flag =false;
                    break; }}if (flag) {
                returni; }}return -1;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = new int[8];
        new Number28().strStr("abababca"."abca");
    }
Copy the code

The results of

KMP algorithm

The implementation code

This is divided into two parts, the partial match table. The partial match table is then used to find the position of the string

    /** ** KMP */
    public int strStr(String str, String target) {
        int tLen = target.length();
        if (tLen == 0) {
            return 0;
        }
        // Partially matches the table
        int[] next = getNext(target.toCharArray());
        for (int i = 0, j = 0; i < str.length(); i++) {
            while (j > 0&& str.charAt(i) ! = target.charAt(j)) { j = next[j -1];
            }
            if (str.charAt(i) == target.charAt(j)) {
                j++;
            }
            if (j == tLen) {
                return i - tLen + 1; }}return -1;
    }

    Partial Match Table Partial Match Table Partial Match Table Partial Match Table Partial Match Table Partial Match Table Partial Match Table
    public int[] getNext(char[] needle) {
        int len = needle.length;
        int[] next = new int[len];
        int j=0;
        // The first value of next must be 0, so start at 1
        for (int i = 1; i < len; i++) {
            while (j > 0&& needle[i] ! = needle[j]) { j = next[j -1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
Copy the code

The results of

Third, summary

Cry to provoke, how to see porno no poor lift fast AH TNT! I wrote it. What’s wrong with it?

Thank you to see the end, very honored to help you ~♥