Blue Bridge Cup algorithms are Beautiful Chapter 5: String to string Matching (Violent Matching and KMP)

Implement an algorithm that flips a given string. Test example: “This is nowcoder”

The code is as follows:

/ / way
public static String reverseString(String s){
    int len=s.length();
    char[] out=new char[len];
    for (int i = 0; i < len; i++) {
        out[len-i-1]=s.charAt(i);
    }
    return new String(out);
}
2 / / way
public static String reverseString1(String s) {
    return new StringBuilder(s).reverse().toString();
}
Copy the code

Write a method that replaces all Spaces in the string with “%20”. Assume that the string has enough space to store the new characters, that you know the true length of the string (less than or equal to 1000), and that the string is composed of uppercase and lowercase English letters. Given a string iniString as the original string and the string length int len, return the replaced string. Test example: “Mr John Smith “,13: “Mr %20John%20Smith “” Hello World”,12: “Hello%20%20World”

The code is as follows:

2 / / way
public static String replaceSpace(String s){
    return s.replaceAll("\\s"."% 20");
}

1 / / way
public static String replaceSpace2(char[] s,int n){
    int count=n;
    for (int i = 0; i < n; i++) {
        if(s[i]==' '){
            count+=2; }}int p1=n-1;
    int p2=count-1;
    while (p1>0) {if(s[p1]==' '){
            s[p2--]='0';
            s[p2--]='2';
            s[p2--]=The '%';
        }else {
            s[p2--]=s[p1];
        }
        p1--;
    }
    return new String(s,0,count);
}
Copy the code

Given two strings s1 and s2, it is required to determine whether S2 can be included in the string produced by the rotation of S1. For example, given s1= AABCD and s2=CDAA, return true; Given s1= ABCD and S2= ACBD, return false.

Answer:

Formula: If the string s2 is obtained by the rotation shift of string s1, then the string s1.apend(s1) must contain s2!

The code is as follows:

public static boolean checkRotate(String s1,String s2){
    return new StringBuilder(s1).append(s1).toString().contains(s2);
}

System.out.println(checkRotate("AABCD"."CDAA"));// true
Copy the code

Force buckle original problem: 796. Rotate string

Here are the answers:

class Solution {
    public boolean rotateString(String A, String B) {
        if(A.length() ! = B.length())return false;
        boolean result = new StringBuilder(A).append(A).toString().contains(B);
	    returnresult; }}Copy the code

Here refer to silicon valley Korea level teacher video: www.bilibili.com/video/BV1E4…

String matching problem:

There is a string str1= “BBC ABCDAB ABCDABCDABDE” and a substring str2= “ABCDABD”

Now determine if STR1 contains str2 and return the first occurrence if it does, or -1 if it does not

• KMP is a classic algorithm for solving the problem of whether a pattern string has ever appeared in a text string and, if so, where it first appeared
• The KMP algorithm uses the previously judged information to save the length of the longest common subsequence in the pattern string through a next array. Each time when backtracking, it finds the previously matched position through the next array, saving a lot of calculation time
• Reference data: www.cnblogs.com/ZuoAndFutur…

KMP algorithm is used to complete the judgment, and simple violence matching algorithm is not used:

Diagram of thought analysis:

For example, a string Str1 = “BBC ABCDAB ABCDABCDABDE”. Does it contain another string Str2 = “ABCDABD”?

• First, the first character of Str1 is compared with the first character of Str2, and the keyword is moved back one bit:

• Repeat step 1, still not match, move back

• This is repeated until one character of Str1 matches the first character of Str2

• Then compare the string to the next character of the search term, which still matches

• Str1 has a character that does not match Str2

• At this point, the idea is to continue iterating through the next character of Str1, repeating step 1. (This is not wise, because BCD has already been compared, so there is no need to repeat the work. The basic fact is that when the space does not match the D, you actually know that the first six characters are “ABCDAB”. The idea of the KMP algorithm is to try to use this known information, not to move the “search location” back to where it has already been compared, but to move it further back, thus increasing efficiency.)

• How do I get rid of the steps I just repeated? It is possible to calculate a partial match table for Str2, the generation of which is described below

• The first six characters, “ABCDAB”, are known to match Spaces that do not match D. The last matching character B corresponds to”Partial matching value“Is 2, so use the following formula to calculate the number of digits moving backwards:Move digit = Number of matched characters - corresponding partial match valueSince 6-2 equals 4, move the search term back 4 bits.

• Because Spaces don’t match C, the search term moves further back. At this point, the number of matched characters is 2 (” AB “), corresponding to”Partial matching value“0. So,Number of moves = 2-0, the result is 2, so the search term is moved back 2 bits.

• Because the space does not match A, continue moving one bit later.

• Bit by bit, until C and D do not match. As a result,Number of moves = 6 minus 2Continue to move the search term back 4 bits.

• Bit-by-bit comparison, until the last bit of the search term, finds an exact match, and the search is complete. If the search continues (that is, finding all matches),Number of moves = 7 minus 0, and move the search term back 7 places, so it doesn’t repeat itself here.

How did the Partial Match List come about?

The “partial match value” is the length of the longest common element of the prefix and suffix. Take “ABCDABD” for example:

• The prefix and suffix of “A” are empty sets, and the length of the common element is 0.
• “AB“Is prefixed with[A]The suffix for[B], the length of the common elements is 0;
• “ABC“Is prefixed with[A, AB]The suffix for[BC, C], the length of the common element is 0;
• “ABCD“Is prefixed with[A, AB, ABC]The suffix for[BCD, CD, D], the length of the common elements is 0;
• “ABCDA“Is prefixed with[A, AB, ABC, ABCD]The suffix for[BCDA, CDA, DA, A], the common element is “A”, the length is 1;
• “ABCDAB“Is prefixed with[A, AB, ABC, ABCD, ABCDA]The suffix for[BCDAB, CDAB, DAB, AB, B], the common element is “AB” and the length is 2;
• “ABCDABD“Is prefixed with[A, AB, ABC, ABCD, ABCDA, ABCDAB]The suffix for[BCDABD, CDABD, DABD, ABD, BD, D], the length of the common elements is 0.

The essence of “partial matching” is that sometimes there will be a repetition at the beginning and end of the string. For example, if “ABCDAB” contains two “AB”, its “partial match” will be 2 (the length of “AB”). When the search term moves, the first “AB” moves back 4 bits (string length – partial match) to get to the second “AB” position.

KMP algorithm to solve the string matching problem code is as follows:

public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = kmpNext("ABCDABD"); // [0, 1, 2, 0]
        System.out.println("next=" + Arrays.toString(next));
        int index = kmpSearch(str1, str2, next);
        System.out.println("index=" + index); / / 15

    }

    / * * *@paramStr1 Source character string BBC ABCDAB ABCDABCDABDE *@paramStr2 substring ABCDABD *@paramNext partial match table, which is the partial match table corresponding to the substring [0, 0, 0, 0, 1, 2, 0] *@returnIf -1 is not matched, otherwise return the first matched position */
    public static int kmpSearch(String str1, String str2, int[] next) {
        / / traverse
        for (int i = 0, j = 0; i < str1.length(); i++) {
            Str1.charat (I)! = str2.charat (j), to resize j
            // The core point of the KMP algorithm can be verified...
            while (j > 0&& str1.charAt(i) ! = str2.charAt(j)) { j = next[j -1];
            }

            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {// find j = 3 I
                return i - j + 1; }}return -1;
    }

    // Get a partial list of matching values for a string (substring)
    // ABCDABD ---> [0, 0, 0, 0, 1, 2, 0]
    public static int[] kmpNext(String dest) {
        // Create a next array to hold part of the matching values
        int[] next = new int[dest.length()];
        next[0] = 0; // If the string is part of length 1, the matching value is 0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            / / when the dest. CharAt (I)! = dest.charAt(j), we need to get new j from next[J-1]
            Dest. charAt(I) == dest.charAt(j) == dest.charAt(j
            // This is the core point of the KMP algorithm
            while (j > 0&& dest.charAt(i) ! = dest.charAt(j)) { j = next[j -1];
            }

            // If dest.charAt(I) == dest.charAt(j), the partial matching value is +1
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        returnnext; }}Copy the code

Force button string related exercises:

• Pointer to Offer 48. Longest substring without repeating characters
• 3. The oldest string without repeating characters
• 5. The longest subroutine string