Now, the brute force algorithm is too slow for us because if a text has a billion characters and the pattern has a 1,000 characters, then it will take a very long time to process an algorithm which works in time, length of the text times length of the pattern, because it will take a trillion operations to perform this algorithm. We want to make the algorithm faster, and the main idea for that is that we can actually skip some of the positions where we compare the pattern to the corresponding substring in the text in the brute force algorithm. Let's see this example. At first, we tried to compare the pattern to the substring starting from Position 0 in the text. We always need to do that. Assume that as in this example, our pattern occurs in the text starting from position number 0. The whole pattern is equal to the corresponding substring. What happens if we try to move our pattern just one position to the right? Can our pattern actually occur in the text? Well, to check that we would need to compare the pattern to the substring of the text starting in position number 1. But we know that the whole pattern is equal to the substring starting Position 0. The substring of the text starting Position 1 is also partially a substring of the pattern itself. It is the same as if we try to compare the pattern to the substring of the pattern starting in Position 1. We see that the first character of the pattern is not equal to the first character of this substring. There is no point in moving the pattern just one position to the right. What if we move our pattern two positions to the right? We would need to compare it to the substring of the text starting in Position 2, which is the same as comparing the pattern to the substring of the pattern itself starting in Position 2. Again, the first character of the pattern is not equal to the character at Position 2. There is no point to moving there. What if we move our pattern even further three positions to the right? Well, then we see that the first position of the pattern at least is the same as the third position of the pattern. We can move our pattern three positions to the right, and it is at least possible that there will be some occurrence of the pattern in the text. It makes sense to move the pattern three positions to the right and try to compare it to the text. However, it doesn't occur in this position because the second pattern character is not equal to the corresponding character of the text. But we need to check this position because just based on the pattern itself and its previous occurrence in the text, we cannot say whether it is possible or not possible for the pattern to occur starting in this position. Now, let's look at another example with another text on the longer pattern. In this case, when we compare the pattern to the start of the text, it turns out that there is no occurrence there. However, there is a pretty long common prefix of the pattern and the text. In this case, it also can give us an idea that it doesn't make sense, for example, to move this pattern just one position to the right. Because then we would compare our pattern to the substring of this substring, which is common between the pattern and the text basically with the pattern in Position 1, but letters A and B are different, so it doesn't make sense to move the pattern just one position to the right and also two positions and three positions also doesn't make sense. The first position where it does make sense to compare these pattern to the text again, is position number 4, where there is again letter A in the common substring of the pattern and the text. We see that not only the first character of the pattern corresponds to the position number 4, but also the second character B is also equal to the next character. There's really a chance that if we move our pattern four positions to the right, there'll be an occurrence. We do that, and we compare the pattern to the substring of the text starting in position number 4, and it turns out that there is an occurrence indeed. What happens in this example? Again, there is no occurrence of the pattern starting from Position 0, but there is a substring of Length 6, which is a common prefix of the pattern and the text. Again, we see that there is a A, B in the beginning of the pattern and then A, B in the end of this common substring. We could move our pattern four positions to the right and there potentially could be a occurrence of the pattern in the text. However, if we think a little longer, we will see that not only ab in the beginning of the pattern is equal to ab in the end of the common substring, but there is a longer such comparison because the beginning of the pattern, the prefix of the pattern ab, ab is equal to the end of the common sub stream ab, ab. Actually, we can move our pattern just two positions to the right, and already there will be a potential occurrence of the pattern. So we just move our pattern two positions to the right, and this ab, ab in the beginning of the pattern coincides with the ab, ab at the ends of the longest common prefix of the pattern in position zero of the text. Now we again compare the pattern with the text starting from this position. It turns out that there is no appearance. However, there is a common substring of length six and is the same substring, and so it again makes sense to move the pattern just two positions to the right because ab, ab is equal to ab, ab. We move our pattern just two positions to the right and we find an occurrence of the pattern. We see that in different situations, we can skip many of the positions where we don't actually need to compare pattern to the text, and the general rule which we apply there, we need to find the longest common prefix of the pattern and the substring to which we're comparing the spectrum in the text, and then we need to find the longest prefix of this common substring, which is the same as the suffix of the same stream. Then just move this pattern so that this prefix goes to the same position as the suffix. This is the least amount that it makes sense to move the pattern to the right, because if you move it less than there will be no coincidence. To make this more formal, we will define border of a string. Border of a string is a prefix of this string, which is equal to the suffix of the string. But the whole string is not considered to be a border. For example, for a string, "arba" letter a is "a" border because there is a prefix "a", and the suffix "a" for string "abcdab" "ab" is a border because there is a prefix "ab" and the suffix "ab", and for a string "ababab" from the third example, we consider "abab" is a border because there is both a prefix "abab", first four letters. Also a suffix "abab", the last four letters of the same string. For example, for a string "ab", string "ab" is not its border because although it is both a prefix and the suffix, it is equal to the whole string, and this case we don't consider a border. To formalize our intuition about how we can move the pattern and along the text. Let's assume that we've already compared the pattern to some substring of the text, and we found the longest common prefix u, which is both a prefix of the pattern and the corresponding substring of the text. Now we need to find w, which is the longest border of u, and then we can move the pattern P so that the suffix of the u in text is above the prefix of u in the pattern, and so that w is under w. This is basically the rule. When we find the longest border w, we need to move so that the left w of p is under the right w of t, and this is how we can skip some of the comparisons. Now we know that almost always you can skip at least some of the comparisons, but we shouldn't really miss any of the bedroom occurrences in the text. We need to move our pattern really safely so that we don't miss any of the occurrences because we want all positions where pattern occurs in the text. The question is, is our new rule really safe? Is it safe to shift the better in this way? Can we prove that actually by moving the bedroom this way, we won't miss any of the currencies of the bedroom of the text? We'll answer that question in the next video.
