Finding the position of one string (pattern string) in another string (main string) is called string pattern matching.

1. Naive pattern matching

For the main string S and the mode string T, pointers I and j are set respectively, assuming that the subscript of the string starts from 0, and I and J point to the zero position of each string at the beginning. At the beginning of the N-pass matching, I points to the n-1 position in the main string S, J points to the 0 position of the pattern string T, and then compares backwards one by one. If every character i n T is equal to that in S, the matching is successful. Otherwise, when a character is not equal, I redirects to the nth position of S, J redirects to the tenth position of T, and continues the n+1 matching.

The time complexity is O(n*m), where N and m are the lengths of the main string and the mode string, respectively.

 /**
 * @param source Main string
 * @param pattern Pattern string
 * @param pos The starting position in the main string
 * @return Successful matching returns the pattern string at the beginning of the main string from pos, failed matching, returns - 1
 */
public static int index(String source,String pattern,int pos){
	// Location in the main string
	int i= pos;
	// Pattern String Location
	int j = 0;
	char[] src = source.toCharArray();
	char[] ptn = pattern.toCharArray();

	while (i<src.length && j<ptn.length){
		if (src[i] == ptn[j]){
			// Current Character Matching Successful
			i++;
			j++;
		}else {
			i = i - j +1;
			j = 0;
		}
	}

	if (j == ptn.length){
		return i - j;
	}else
		return -1;
}

 

2. KMP algorithm

next Array Solving Algorithms:

For the pattern string T, next[j] represents the longest common string length of the prefix and suffix in the substring composed of the first j characters of T.

public class KMP {

    /**
     * Getting Partial Matching Table
     */
    private static int[] getNext(String pattern){
        char[] ptn = pattern.toCharArray();
        int[] next = new int[pattern.length()];

        // The first position is -1 and the second position is 0.
        next[0] = -1;next[1] = 0;

        int k = 0;

        for (int j = 2; j < ptn.length; j++) {
            k = next[j-1];
            while (k != -1){
                if (ptn[j-1] == ptn[k]){
                    next[j] = k+1;
                    break;
                }else {
                    k = next[k];
                }
                // When k==-1 jumps out of the loop, next[j] = 0
                next[j] = 0;
            }
        }
        return next;
    }

    /**
     * KMP pattern matching
     * @param src Main string
     * @param pattern Pattern string
     * @return The first occurrence of a matched successful return pattern string in the main string
     * Matching failed, return - 1
     */
    public static int KMPMatch(String src,String pattern){
        char[] S = src.toCharArray();
        char[] T = pattern.toCharArray();
        int next[] = getNext(pattern);
        /**
         * i: Location in the main string
         * j: Location in pattern string
         */
        int i = 0,j = 0;
        while (i<S.length && j<T.length){
            if (j == -1 || S[i] == T[j]){
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if (j == T.length){
            return i-j;
        }else {
            return -1;
        }
    }

    public static void main(String[] args){
        String src = "ababaaaba";
        String pattern = "aa";
        int index = KMPMatch(src,pattern);
        System.out.println(index);
    }
}

 

Reference resources: https://www.cnblogs.com/imzhr/p/9613963.html