Check and set
1. The introduction of
A parallel lookup set is a structure that can quickly combine sets.
Assuming that there are five samples ABCDE, we will form A set of each sample separately: {A}, {B}, {C}, {D}, {E}.
Now we need to provide two operations externally:
- The first is: query whether any two samples belong to the same set isInSameSet(a, b).
- The second is: merge any two sets of samples that are not the same set into union(a, b).
There are many constructs that can be used to implement both of these functions. But to make the two functions run fast and complex, you can’t do it with classical constructs.
-
If you do it with a linked list, then union(a, b) is very fast, and goes to O(1); But isInSameSet(a, b) is slow, O(N), because you need to traverse the entire list.
-
If you use a hash table, then isInSameSet(a, b) is very fast and can reach O(1); However, union(a, B) is slow and the time complexity of data migration between hash tables is high.
What structure can we design so that isInSameSet(a, b) and Union (a, b) both have O(1) time complexity? Check and set.
Principle 2.
A special logical graph structure is used to represent and look up sets.
Each sample is a Node in the graph, and each Node will have a pointer that will point to the Node itself when the parallel lookup is initialized.
The implementation logic of isInSameSet(a, b) is: to find the representative nodes of sample A and sample B respectively. If the representative nodes are the same node, it means that sample A and sample B are in the same set. If they are not the same node, then sample A and sample B are not in the same set.
A representation node is a representation of a set.
Representative Node search method is: from the current sample Node pointer points to traverse, until the traversal pointer points to its own Node, the Node is the representative Node of Node.
The implementation logic of union(a, b) is as follows: First, isInSameSet(a, b) is called to determine whether sample A and sample B are in the same set. If so, no operation is required. If not, you can merge. The specific implementation of merging is to point the pointer of the representative node of the set with fewer nodes to the representative node of the set with more nodes (if the two sets have the same number of nodes, the pointing order is arbitrary).
3. The optimization
And lookup set has a very important optimization, optimization is based on the pointer to traverse the process.
As shown in the figure above, assume that at some point in time the structure is integrated, and assume that isInSameSet(a, g) or union(a, g) is now called (the union base still calls isInSameSet). At this point, nodes A and G will start traversing according to their pointer until they reach the node position where the pointer points to them. A pointer points to itself, so no traversal is required; G needs to traverse F, E, and B in order to find A.
The optimization operation is to “flatten” the path traversed by G in g — > F — > E — > b — > A.
The operation of flattening is that the Pointers of all nodes along the traversal path point to the last representative node, that is, the Pointers of nodes G, F, B and E point directly to A.
Without tuning and looking up the set, the performance bottleneck is obvious. If the time complexity of one operation of the parallel lookup set is too high, it must be caused by a node traversing to search for the one-way linked list representing the node, which is the only problem that the parallel lookup set needs to be optimized.
The “flattening” operation continuously reduces the length of a one-way list without violating the original structure.
So how do you evaluate why “flat” optimizations reduce the time complexity of a set lookup operation?
The proof was too complicated, and it took 25 years to prove the collection until 1989, when it was invented in 1964. For a detailed proof, see chapter 23 of Introduction to Algorithms.
We’ll just say the conclusion: if there are N samples, the average cost of a single findRepresentativeNode is O(1) after the number of findRepresentativeNode calls has approached the O(N) level or higher. In other words, when the sample size is large and findRepresentativeNode is called for a limited number of times, the complexity of a single call to findRepresentativeNode can be guaranteed to be very low. However, if the call of findRepresentativeNode is very frequent, so frequent that it approaches the number of samples, then the more frequent the call, the lower the complexity of a single call of findRepresentativeNode, up to O(1), and the constant is very small, no more than 6.
4. To achieve
public class UnionFindSet<V> {
// Node type
static class Node<V> {
/ / sample
public V value;
public Node(V value) {
this.value = value; }}// sample -- Node table
public HashMap<V, Node<V>> nodeMap;
// Node -- parent Node table
public HashMap<Node<V>, Node<V>> fatherMap;
// represent Node -- table corresponding to the total number of nodes in the corresponding set (only represent nodes will be stored in this table, and include represent nodes when calculating the total number)
public HashMap<Node<V>, Integer> sizeMap;
// The List must be initialized and all samples must be registered in the List.
public UnionFindSet(List<V> samples) {
nodeMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
for (V sample : samples) {
// Build each sample into a Node
Node<V> node = new Node<V>(sample);
// Map the sample to Node
nodeMap.put(sample, node);
// Initialize each node with a pointer to itself
fatherMap.put(node, node);
// When initialized, each Node forms a collection, and each Node represents a Node
sizeMap.put(node, 1); }}// Find the representative Node of the collection to which the Node belongs (flat optimization)
private Node<V> findRepresentativeNode(Node<V> node) {
// Use a stack to assist optimization
Stack<Node<V>> stack = new Stack<>();
// until you reach the position where the pointer points to itself
while(fatherMap.get(node) ! = node) {// Push all nodes along the route
stack.push(node);
// node is assigned to its parent
node = fatherMap.get(node);
}
// Perform flat optimization
while(! stack.isEmpty()) {// Place Pointers to all nodes along the path
fatherMap.put(stack.pop(), node);
}
// Returns the representative node
return node;
}
// Check whether two samples a and B are in the same set
public boolean isInSameSet(V a, V b) {
// Make sure samples A and B are registered
if (nodeMap.containsKey(a) && nodeMap.containsKey(b)) {
// Check whether the representative nodes of the two samples are the same
return findRepresentativeNode(nodeMap.get(a)) == findRepresentativeNode(nodeMap.get(b));
}
return false;
}
// If sample A and sample B belong to different sets, merge the two sets
public void union(V a, V b) {
// Make sure samples A and B are registered
if (nodeMap.containsKey(a) && nodeMap.containsKey(b)) {
// Fetch their representative node
Node<V> aRNode = findRepresentativeNode(nodeMap.get(a));
Node<V> bRNode = findRepresentativeNode(nodeMap.get(b));
// If the representative nodes are not the same, merge the set
if(aRNode ! = bRNode) {// Determine which set has more nodes
Node<V> moreNode = sizeMap.get(aRNode) > sizeMap.get(bRNode) ? aRNode : bRNode;
Node<V> lessNode = moreNode == aRNode ? bRNode : aRNode;
// Point a delegate node with less set nodes to a delegate node with more set nodes
fatherMap.put(lessNode, moreNode);
// Update the number of nodes in the merged collection
sizeMap.put(moreNode, sizeMap.get(lessNode) + sizeMap.get(moreNode));
// The set with a small number of nodes is no longer a representative nodesizeMap.remove(lessNode); }}}}Copy the codeIsland problem
1. Classic questions
Topic:
There are only two values of 0 and 1 in a matrix, and each position can be connected to its top, bottom, left and right positions. If you have a 1 joined together, that part is called an island. How many islands are there in a matrix?
For example, the matrix below has three islands.
0, 0, 1, 0, 0, 0
0, 0, 1, 0, 0, 0
0, 0, 0, 0, 1, 0
0, 0, 0, 0, 1, 0
Analysis:
This is a typical interview question, which can introduce a structure.
The classic problem is easily solved by first defining an infection process, and then traversing the matrix. Whenever a 1 is encountered during the traversal, the wigorous command is called to connect all 1’s that can be connected to the left, right, and lower parts of the 1 and set them all to 2’s. Until the matrix traversal is complete, at which point a few calls to the galleys will have several islands.
If you use the matrix given in the title, the recursive call tree for A WigOROUS would look like this:
The time complexity of the whole process is O(NM), where N is the width of the matrix and M is the length of the matrix.
Although the algorithm has a recursive process, but the time complexity is not high, only a matrix scale.
How to estimate the time complexity, let’s see how many times each position in the matrix is accessed. In the global traversal phase, each location is accessed once. In the Wigorous phase, each location is visited at most once by its top, bottom, left, and right. In general, each location will be called at most five times, a finite number. Therefore, the time complexity is O(5NM), and the constant term is O(NM).
Code:
public static int islandProblem(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
// How many times to call a wigorous
int count = 0;
for (int i = 0; i < matrix.length; i ++) {
for (int j = 0; j < matrix[i].length; j ++) {
if (matrix[i][j] == 1) {
// Perform the infection process
infect(matrix, i, j);
// The number of infections increasescount ++; }}}return count;
}
public static void infect(int[][] matrix, int i, int j) {
// Base case boundary filter
if (
i < 0 || i >= matrix.length
|| j < 0|| j >= matrix[i].length || matrix[i][j] ! =1) {
return ;
}
// set itself to 2
matrix[i][j] = 2;
// Set all 1's connected to the position to 2's
infect(matrix, i - 1, j);
infect(matrix, i + 1, j);
infect(matrix, i, j - 1);
infect(matrix, i, j + 1);
}
Copy the code2. Expand the problem
Problem: How to design a parallel algorithm to solve a classical problem.
Analysis:
The default environment for most questions encountered in interviews and ACM is a single-CPU, single-memory system, focusing only on the logic of the algorithm. However, in the interview process, there will also be problems with parallel algorithms, which do not need to be implemented in code, just need to explain the process.
When the time complexity of the classical solution is well controlled, why design a parallel algorithm to solve this problem?
Suppose the matrix is so large that if you use the classical solution, you can only use one machine to solve it, which is extremely slow. If the parallel algorithm is used, we need to design a strategy of fragmentation and merger for the matrix, so that multiple machines can calculate the number of islands in the matrix in parallel, and the efficiency is geometrically increased.
Solution:
Before designing parallel algorithms, you need to understand and look up the very important structure of sets.
Suppose we first discuss acceleration using two cpus in parallel:
If we divide the matrix among different cpus for calculation, the number of islands may rise. For example, in the following matrix, we find that all the ones in the original matrix are joined together, so there is only one island. If we split the matrix down the middle, CPU1 counts the number of islands in the left half of the matrix, and CPU2 counts the number of islands in the right half of the matrix, then CPU1 will count two islands, and CPU2 will count two islands, for a total of four.
In fact, there is only one island, but why are there multiple islands after partitioning the matrix?
Because the partitioning process destroys the original connectivity. Therefore, we also need to design a combination matrix scheme to be able to calculate the number of correct islands.
The scheme of merging matrix is as follows:
After CPU1 calculates the number of islands in the left half of the matrix, it uses the GALleys process to gather information about infection points on the boundaries (boundaries are delimited boundaries). After CPU2 calculates the number of islands in the right half of the matrix, it also uses the GALleys process to gather information about infection points along the boundary.
How do you gather information about infection sites? CPU1 should first record the first infected initial point A in the left half of the matrix, and then record all boundary points infected by A. CPU1 then records the second infected initial point B in the left half of the matrix, and then records all boundary points infected by B. CPU2 records the first infected initial point C in the right half of the matrix, and then records all boundary points infected by C (which is itself an infected boundary point). CPU2 then records the second infected initial point D in the right half of the matrix, and then records all boundary points infected by D (D is itself an infected boundary point).
Register A, B, C, and D into the collection and initialize it. Start as A set {A}, {B}, {C} and {D}, respectively. And then we’re going to see if the two points that touch each other are part of the same set. For example, in the two points circled in the figure above, the left point is the boundary point infected by B, and the right point is the boundary point infected by C. B and C do not belong to the same set, so the set of B and C needs to be merged into {B, C}, and then the total island number is reduced by one (because the two points whose boundaries collide are connected in the original matrix). If B and C belong to the same set, it means that the previously discussed link path already includes the two points where the boundary touches, and the total island number remains unchanged.
After all boundary collisions are discussed, the matrices divided by the two cpus are merged successfully. The total number of islands is the number of islands of the original matrix.
Why is this method fast?
The classic solution is for a CPU to traverse the matrix from left to right and top to bottom to get the result; Now it is time for CPU1 and CPU2 to traverse half of the matrix at the same time, and finally one CPU3 to process the boundary collision point.
In the case of multiple cpus working in parallel, we can divide the matrix into blocks, and each CPU processes its own block first and then the boundary information (the boundary information is processed in the same way as two cpus). For example, after CPU1 processes its own information, it also needs to process the boundary information of the four edges.
3. Summary
The solution to the extended problem follows the idea of MapReduce, which is the process of converting an algorithm into parallel computing and being able to integrate the correct results. Map is to process different blocks of a whole in parallel, and Reduce is to integrate information of different blocks.
This solution is much more advanced than the classic Hadoop and Spark Reduce solution, which is a very strong algorithm design.
KMP algorithm
1. The introduction of
The most famous application of KMP algorithm is the substring problem.
Topic:
Now we have str1=” abCD1234EFg “and str2=”1234”. How can we determine if str2 is a substring of str1?
Note that the substring must be consecutive, for example “1234F” is not a substring of “abCD1234EFg”, but “1234E” is.
Analysis:
In this case, if the violent solution is used, the attempt method is to try str1 from left to right to see if each character can match str2.
Violent solution In an extreme case, the time complexity can be very high. For example, str1=”1111111112″, str2=”11112″. To use the brute force method, str1 is matched five times from the first character 1 and found unmatched five times from the second character 1, and so on until the last section of str1 is matched. If STR1 is long N and STR2 is long M, then the time complexity is O(NM), which means that every step of STR1 needs to traverse the whole str2.
If the KMP algorithm is used to solve the problem, the return type is not Boolean, but the subscript of the first character of the substring in STR1, or -1 if not included.
The core idea of KMP and the violent solution is the same, they both try str2 from left to right for each character in STR1, but KMP is accelerated.
Violent solution:
public static boolean findSubStr(String str1, String str2) {
if (str1 == null || str2 == null || str1.length < str2.length) {
return false;
}
return process(str1.toCharArray(), str2.toCharArray());
}
public static boolean process(char[] c1, char[] c2) {
The // flag defaults to false, so that str1 and str2 will return false if they have no intersecting characters
boolean flag = false;
// walk through str1
for (int i = 0; i < c1.length; i ++) {
// Try to match every character in str1 to str2
if (c1[i] == c2[0]) {
// As long as one character is matched, we expect the match to be successful
flag = true;
Str1 and str2 are matched character by character
int k = i + 1;
for (int j = 1; j < c2.length; j ++, k ++) {
// If there is only one character different during the matching process, the matching fails
if(c1[k] ! = c2[j]) { flag =false;
break; }}}}return flag;
}
Copy the code2. Maximum matching length
Before using KMP algorithm to solve the substring problem, we first need to understand the concept of the longest prefix and suffix matching length.
The matching length of the longest prefix and suffix is the information that each character in the substring (STR2) needs to carry, independent of the corresponding character, but related to all the characters preceding the corresponding character.
For example, if we have a string “abbabbk”, we want to know the matching length of the longest prefix followed by the suffix of the k character.
First we need to get the string “abbabb” before the k character. Then we find the maximum matching length of the prefix and suffix of the string “abbabb” is 3. The k character carries 3 information.
Neither prefix nor suffix can be taken to the whole string.
If the character is preceded by no string, the information carried by the character is -1.
The character at position 0 of the string is artificially assigned to carry -1 and the character at position 1 carries 0.
3. Speed up the process
The key to using KMP to speed up this problem is that each character in STR2 carries the maximum matching length of prefix and suffix.
Suppose str1 = “… oabbcefabbckbc……” , str2 = “abbcefabbcg…” . The first character o displayed in STR1 is bit i-1, assuming that the current str1 matches STR2 from bit i-1 (the previous matching process is ignored).
Use the classic method:
Characters after the i-th bit of STR1 are matched with characters of STR2 in sequence. When str1 matches the i-th bit of STR1, it is found that the characters of str2 cannot match the i-th bit of STR1, and the matching operation from the i-th bit fails. Thus, STR1 abandons the possibility that the i-th bit will match the substring successfully, and the matching pointer jumps from the i-th + 10 bit of STR1 to the i-th + 1 bit. Characters after the i-th + 1 bit of STR1 are then matched with characters at the 0th bit of STR2 (str2 slides one bit to the right). And so on.
Acceleration using KMP algorithm:
[-1, 0, 0, 0, 0, 1, 2, 3, 4……] .
Characters after the i-th bit of STR1 are matched with characters of STR2 in sequence. When str1 matches the i-th bit of STR1, it is found that the characters of str2 cannot match the i-th bit of STR1, and the matching operation from the i-th bit fails.
According to the maximum matching length of prefixes and suffixes, the maximum matching length of the first 11 bits is 4 corresponding to the 10th character. Therefore, it can be determined that the maximum prefix and suffix before the 10th character G of STR2 are “ABbc”.
Str1’s matching pointer is left untouched, and character matching continues with str2’s fourth bit (the last bit of the largest prefix).
4. Analyze the
To understand what KMP’s second action really means? You can see this by looking at the comparison object twice.
Just like the classical method, str1 does not attempt the possibility that the I + 1 bit can be matched successfully after the initial matching operation of str1 fails. However, STR1 does not attempt the possibility that the I + 2 bit can be matched successfully. Instead, it directly attempts the probability that the I + 6 bits will match (equivalent to str2 sliding right (the subscript of the first digit in the largest suffix – the subscript of the first digit in the largest prefix) bits), meaning that STR1 will match directly from str2’s largest suffix in STR1.
But the I + 6 bits of STR1 and the 0 bits of STR2 are confirmed to be overlapped in the last round of matching, both of which have the maximum prefix/suffix of “ABBC”. In order to accelerate better (constant acceleration), the actual comparison can directly skip the coincidence part and start the comparison.
So instead of trying to match from the I + 6 position, STR1 matches directly from the I + 11 position, because the I + 6 to the I + 9 position of STR1 coincides with the 0 to 3 position of STR2. Only after bit I + 10 of STR1 can a match fail.
So now we need to prove a point: why does a match from the I + 1 bit of STR1 to the I + 5 bit of str1 always fail?
5. Proof
Why does a match from the I + 1 bit of STR1 to the I + 5 bit of str1 always fail?
Array [-1, 0, 0, 0, 0, 1, 2, 3, 4……] The relevant.
Abstract the above proof problem: the proof that any k between the i-th and j-th bits of STR1 [I +1, J-1] starts to match is bound to fail.
The proof assumes that the I to (x-1) bits of STR1 are exactly the same as the 0 to (y-1) bits of str2.
Using proof by contradiction, we assume that the KTH bit of str1 starts matching, and the result is a successful match.
We know that no matter what bit str1 matches from, it matches from the 0th bit of str2, and if the match is successful, it means that the segment from the KTH bit of STR1 to the X bit of str1 must be exactly the same as the segment from the 0th bit of str2 to the x-k bit of str2.
So the period from the KTH bit of str1 to the x-1 bit must be exactly the same as the period from the 0th bit of str2 to the x-k-1 bit.
And since only the x-position of STR1 and the y-position of STR2 were different in the last round of matching, the k-position to (x-1) position of STR1 must be exactly the same as the (y-x + K) position to (y-1) position of STR2.
By equivalence swap, the segment from the 0th bit of STR2 to the (x-k-1) bit must be exactly the same as the segment from the (y-x + K) bit of str2 to the (y-1) bit.
Since the KTH bit of str1 is less than the JTH bit, the distance from the KTH to the X bit of str1 must be larger than the distance from the JTH to the X bit.
So the corresponding segment from the 0th bit of str2 to the (x-k-1) bit must be longer than the longest prefix of the original y-th bit.
Because the distance from the 0th bit of str2 to the x-k-1 bit is the same as the distance from the y-x + k bit of str2 to the y-1 bit.
The corresponding (y-x + K) bit to (y-1) bit of str2 must therefore be longer than the longest suffix of the original y-bit.
And since the period from the 0 digit of str2 to the (x-k-1) digit is also the prefix of the Y digit, and the period from the (y-x + k) digit of str2 to the (y-1) digit is also the suffix of the Y digit.
So the Y bit of the original STR2 has a prefix and suffix longer than the longest prefix and suffix. Since the longest prefix and suffix have been given, they contradict each other and the hypothesis is not valid.
6. Complete the process
In fact, the entire KMP process is str2 moving all the way to the right.
We put aside the process of KMP constant optimization and carefully analyze the essential process of KMP acceleration.
Why is KMP fast? Take str1 a~ E for example, using the classical method requires 17 comparisons, while using KMP only requires 4 comparisons. If constant acceleration of KMP is added, the comparison will be faster in 4 comparisons.
Among them, ①, ②, ③ and ④ are the comparative positions of STR1 and STR2 at the beginning of the four matches, and actually represent the complete acceleration process of KMP to a~ E in STR1.
When the matching pointer points to position ① of str1, the matching fails until e and w do not match.
Then find the longest prefix and suffix of w in STR2: abbsabb. The matching pointer points to position ② and starts matching until it is found that e and T do not match, so position ② fails to match.
Then find the longest prefix and suffix of t in STR2: ABB. The matching pointer points to position ③ until it is found that e and S do not match, so position ③ fails to match.
Then find the longest prefix and suffix of s in STR2: none. The matching pointer points to position ④ and starts to match. It is found that e and A do not match. Therefore, position ④ fails to be matched.
In STR1, a~ E have all been matched with STR2, and str2 cannot be matched at any position. Therefore, the matching pointer points to the last digit of E to start matching, and the operation of position ① continues in a cycle until the last digit of STR1 ends.
7. To achieve
The implementation process includes constant acceleration.
// The return value is the starting index of the substring in str1
public static int findSubStr(String str1, String str2) {
if (str1 == null || str2 == null || str1.length() < str2.length()) {
return -1;
}
return process(str1.toCharArray(), str2.toCharArray());
}
public static int process(char[] str1, char[] str2) {
// i1 is a pointer to str1, i2 is a pointer to str2
int i1 = 0;
int i2 = 0;
// Get the longest prefix and suffix for all str2 characters
int[] next = getMaximalPrefixAndSuffix(str2);
// The matching process is terminated whenever i1 is out of bounds or i2 is out of bounds (i1 and i2 may also be out of bounds)
while (i1 < str1.length && i2 < str2.length) {
// There are only three cases of KMP acceleration
if (str1[i1] == str2[i2]) {
Str1 and str2 continue matching in parallel
i1 ++;
i2 ++; // i2 will move forward only if the matching characters are equal
} else if (i2 == 0) { // next[i2] == -1
// The position of the string is not the same, but the matching pointer of str2 is at the position of 0, indicating that i2 jumps to the position of 0, which means that there is no position of str1 before str2 can be matched successfully
// The str1 match pointer moves back one bit to start the next match with str2
i1 ++;
} else {
// The corresponding position is different, and the matching pointer of str2 is not at 0, so i2 needs to jump to the next bit of the longest prefix for the next comparison
// This process is the KMP constant acceleration operationi2 = next[i2]; }}// If i2 is out of bounds, then str2 is matched successfully in str1, and the first neutron string of STR1 is returned
// If i1 is out of bounds, then none of str1 can match str2 successfully and -1 is returned
return i2 == str2.length ? i1 - i2 : -1;
}
// The essence of counting the maximum prefix is to determine the maximum prefix for each bit of STR2. The estimated maximum prefix will shrink each round if no match is successful until it shrinks to 0, indicating that there is no maximum prefix at this position
public static int[] getMaximalPrefixAndSuffix(char[] str2) {
// If str2 has only one character, it must be next[0]
if (str2.length == 1) {
return new int[] {-1};
}
// If there is more than one character, assign next[0] and next[1] manually
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
// str2 cursor, starting from str2[2] and filling in next
int i = 2;
// prefix is the subscript of the last digit of the longest c[I] prefix currently most likely
int prefix = 0;
// Next is fully filled when I is out of bounds
while (i < str2.length) {
if (str2[i - 1] == str2[prefix]) {
Str2 [I] = str2[I] = str2[I] = str2[I]
// The i-th bit is successfully matched
next[i ++] = ++ prefix;
} else if (prefix > 0) {
// If the first digit of str2[I] is not the same as the last digit of str2[I], the longest prefix must be shrunk and prefix must jump forward
// prefix needs to jump to the last digit of the longest c[prefix] prefix
// The current I bit fails, and the next round continues to match the I bit
prefix = next[prefix];
} else {
Str2 [I] has no longest prefix and is set to 0
// The i-th bit is successfully matched
next[i ++] = 0; }}return next;
}
Copy the codeComplexity 8.
First demonstrate the complexity of the while loop in the process method:
while (i1 < c1.length && i2 < c2.length) {
if (c1[i1] == c2[i2]) {
i1 ++;
i2 ++;
} else if (i2 == 0) {
i1 ++;
} else{ i2 = next[i2]; }}Copy the codeBy looking at the code, we can see that i1 and i2 increase in the first branch; I1 increases in the second branch; In the third branch i2 goes down.
To estimate the complexity of while, we need to assume two quantities, the first of which is i1 and the second is i1-i2.
Assuming that str1 has length N, then i1 and i1-i2 are both at maximum N.
We’re going to look at the effects of each of the three branches of the loop on these two quantities.
The first branch of the loop, i1 and i2 increase together. So i1 goes up, i1 minus i2 stays the same.
The second branch of the loop, i1 increases. So i1 goes up, i1 minus i2 goes up.
The third branch of the cycle, i2 decreases. So i1 stays the same, i1 minus i2 goes up.
You can only go one branch at a time, so if you add the ranges of these two things together, the maximum range is 2N (go the second branch, and both are N).
None of the three branches reduces either quantity, so the number of times the loop occurs is tied to the superposition of the range of changes between the two quantities, which is the number of times the while loop, so the total while loop cannot exceed 2N.
Therefore, it can be proved that the time complexity of while is linear and is O(N).
Then prove getMaximalPrefixAndSuffix method of complexity:
public static int[] getMaximalPrefixAndSuffix(char[] str2) {
if (str2.length == 1) {
return new int[] {-1};
}
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int prefix = 0;
while (i < str2.length) {
if (str2[i - 1] == str2[prefix]) {
next[i ++] = ++ prefix;
} else if (prefix > 0) {
prefix = next[prefix];
} else {
next[i ++] = 0; }}return next;
}
Copy the codeThe complexity of the estimated getMaximalPrefixAndSuffix, we also need to assume two quantities, the first is I, second quantity is the I – prefix.
Assuming that str2 is of length M, the maximum value of I is M, and the maximum value of i-prefix is also M.
The first branch of the loop, I and prefix are added together. So I increases and i-prefix stays the same.
The second branch of the loop, prefix, is reduced. So I stays the same and i-prefix increases.
The third branch of the cycle, I increases. So I increases, i-prefix increases.
Each cycle takes only one branch, so if you add the ranges of these two quantities together, the maximum range is 2M (go the third branch, and both are N).
So you can prove getMaximalPrefixAndSuffix time complexity is linear, for O (M).
The overall time complexity is:
Since M must be less than or equal to N, the overall time complexity of KMP is O(N).