Regarding the KMP algorithm, which master can help implement it

I've changed it to C for you.

The algorithm is verified and the first position is displayed.

As follows: include

#include

int getsubstr(char * str,char * substr)

int i,j;

bool flag;

for(i=0 ; iflag=true;

for(j=0; jif(str[i+j]!=substr[j])

flag=false;

break;

if(flag)

return i;

return -1;

int main()

int getsubstr(char * str,char * substr) ;

char a[ 20] ;

char b[ 20 ]

printf("Please enter the source string:" )

scanf("%s",&a) ;

printf("Please enter the string you want to query:") ;

scanf("%s", &b )

int j =getsubstr(a,b) ;

if( j != -1 )

printf("The substring position starts at the %d bit of the source string. ", j+1 );

else printf("No matching substrings found") ;

return 0;

(1) The time complexity of the unimproved pattern matching algorithm is o(n m), but in general, its actual execution time is close to o(n m), so it is still used today.

2) The KMP algorithm appears faster than the unimproved pattern matching only if there are many "partial" matches between the pattern and the main string.

2) The biggest feature of the KMP algorithm is that the pointer indicating the main string does not need to be backtracked, and the main string only needs to be scanned from beginning to end in the whole matching process, which is very effective for processing large files stored in external memory.

The string to be matched is prefixed with many duplicate strings, and the target string also contains a lot, e.g. find 'abababc' in 'abababababababc'

The time complexity of the KMP algorithm is o(n+m), where n is the length of the original string and m is the length of the string.

The core of the KMP algorithm is the NEXT array, which can quickly find the first position with the same prefix as the substring when a certain position is mismatched, and continue to match without repeating unnecessary operations, which greatly reduces the time complexity.

Let's not mention how the next array is generated, but let's explain how to use the next array.

For example, if abababac matches ababac, assume that the parent string is subscripted as i, the substring subscript is j, and the string leader subscript is 1

First, the two strings are aligned.

abababac

ababac

When the match reaches the sixth position, a mismatch is found.

The traditional algorithm will move i to the second bit, j to the first bit, and continue to match.

Namely: abababac

ababac

The KMP algorithm, on the other hand, will directly immobilize the position of J=Next[J],i.

In this case, next[6]=4, i.e., move j to the fourth position.

Namely: abababac

ababac

At this time, the match will continue to be successful. Since i does not move forward, the time complexity is o(n+m).

KMP matches C++**:

int next[100];

char str1[100],str2[100];

void kmp_cmp()

For the next array.

That is, the last position of a substring and its own common prefix.

This may be a bit abstract, but to put it bluntly, it is the longest common prefix that the substring matches with itself with that position as the last bit.

When evaluating the ith position of the next array, all the previous next values of that position have already been calculated, so we can update the value of next[i] at this moment with the help of the previous value of next[i].

So the time complexity is o(2*m).

Take ababac, for example:

Step 1: ababac

ababac

i,j are mismatched at the beginning, i.e., next[2]=0.

Step 2: Ababac

ababac

i,j match in position 3, next[3]=1

Similarly: next[4]=2, next[5]=3, next[6]=4

There is a mismatch at i=6, j=4.

Therefore, j=next[j]+1,i++, that is, the matching string is moved backwards.

Namely: ababac

_ababac

In this case, the two strings are mismatched, next[7]=0

Find the next array **:

int next[100];

char str2[100];

void get_next()

elsej=next[j];

The above is the understanding of the KMP algorithm below, if there are any shortcomings, please forgive me, if there is something you don't understand, please also ask questions.

Well, KMP, I've been thinking about it for a long time, and it's a very ingenious algorithm! You won't be able to read the encyclopedia or something, so I'll hit it by hand....Here's my understanding

For the sake of explanation, I will call the long one the text string and the short one the target string

The conventional matching algorithm shifts the target string to the right one by one, compared to the text string, while KMP jumps to the right

I'll give you a few examples.

For example, if there is a target string of ababaca, the current position matches the first 5, that is, it matches ababa, and the last two do not match.

This shows that the current position of the text string is also ababa

Obviously, it is not possible to move one place to the right, because it can be seen from the target string that the content in parentheses is not equal to that of a(baba).

And it's possible to move two places to the right because you can see that the content in the brackets is equal to the ab, which means that after moving two places, the first three places of the target string are definitely matched, because they also match before the move

For example, if there is a target string abcab, the current position matches the first two abs

Then you need to move 3 positions to the right, because the content in parentheses is the same as that in abc (ab), and it is possible to match after moving

Got it? Limited ability to express themselves....I couldn't have said any better....Specifically**There are a lot of them on the Internet, and there are also in "Introduction to Algorithms" I learned it in the first place!

If you understand, I hope there will be additional points, and your hands are tired to death!!

If you don't understand, just ask......

KMP algorithm and BM algorithm, which are the classical algorithms of prefix matching and suffix matching, respectively.

1. Because each entry in the routing table specifies a network, one destination address may match multiple entries. The most explicit entry, i.e., the one with the longest subnet mask, is called the longest prefix match.

2. The reason why it is called so is because this entry is also the entry in the routing table that matches the high position of the destination address the most.

So what do you tell us about their connection?