Shulou(Shulou.com)06/01 Report--

This article mainly introduces C++ KMP substring search algorithm how to use the relevant knowledge, the content is detailed and easy to understand, simple and fast operation, has a certain reference value, I believe that everyone after reading this C++ KMP substring search algorithm how to use the article will have a harvest, let's take a look.

We learned about string classes before, so the need to find string classes follows. How to find out if there is a substring P in the target string S?

The first thing we can think of must be a simple solution. What is a simple solution? It is to make a comparison one by one, and if the comparison is not successful, move back one place. The code is as follows

Then the solution at this time must not be very good, because its time complexity is O (massin). So how do we optimize it? Let's take a look at the following picture.

From the picture above, we can draw a conclusion: because Pa! = Pb and Pb = = Sb; so Pa! + Sb; therefore, it doesn't make sense for substring p to move 1 bit to the right. Next, we take the example string as an example to analyze and illustrate, as follows

We see that in the first step, the first character fails to match, and then we directly move 1 bit to the right; until the 7th character matching fails, we can see with the naked eye that it is best to move 4 bits to the right; then when we fail to match to the third character, we can see that moving 2 to the right is the best; and so on.

So have we found anything? As long as we know how many places we need to move to the right, we can easily come to a conclusion. Then this area has been discovered by predecessors, and we only need to master this method to solve the problem easily. So what is the great discovery? When matching fails, the number of right shifts is related to the substring itself and has nothing to do with the target string; the number of moving bits = the number of characters that have been matched-the corresponding partial matching value; there is a unique partial matching table for any substring.

Let's look at an example of a partial matching table, as follows

So the question is, how did you get this part of the matching table? First, let's introduce two concepts: prefixes and suffixes. A prefix refers to all the header combinations of a string except the last character, and a suffix refers to all the tail combinations of a string except the first character. Then part of the matching value is the length of the longest common element of the prefix and suffix. We take the string "ABCDABD" as an example, as shown in the following figure.

We see that in the first character A, its intersection is empty, so the match value is 0; in the first two characters, it is also empty, so the match value is also empty; until the fifth character, the intersection is A, so its match value is 1; in the sixth character, the intersection is AB, so the match value is 2; in the last character, the intersection is empty, so the match value is 0.

So we know how to solve partial matching values manually, so how to program to generate partial matching tables in the program?

The key to implementation:

1. PMMT [1] = 0 (the matching value of the element with subscript 0 is 0)

2. Recursive from 2 characters (recursive from characters with subscript 1)

3. Suppose PMT [n] = PMT [n-1] + 1 (the length of the longest common element)

4. When the hypothesis is not true, PMT [n] decreases on the basis of PMT [n-1].

Next, let's implement a program that partially matches the table. The code is as follows

# include # include # include "DTString.h" using namespace std;using namespace DTLib;int* make_pmt (const char* p) / / O (n) {int len = strlen (p); int* ret = static_cast (malloc (sizeof (int) * len)); if (ret! = NULL) {int ll = 0; ret [0] = 0; for (int item1) I 0) & (p [ll]! = p [I]) {ll = ret[ ll-1];} if (p [ll] = = p [I]) {ll++;} ret [I] = ll;}} return ret } int main () {int* pmt = make_pmt ("ABCDABD"); for (int iTuno; I

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.