# Patterns Matching (Naive Patterns Matching, KMP Patterns Matching)

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.

1. next = -1, next=0.
2. In solving next[j], let k=next[j-1],
3. Comparing the values of T[j-1] and T[k],

If T[j-1] equ a ls T[k], then next[j]=k+1.

b. If T[j-1] does not equal T[k], let k=next[k], if k equals - 1, then next[j]=0, otherwise jump to 3.

```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 = -1;next = 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

Added by plaggypig on Mon, 07 Oct 2019 07:11:27 +0300