How is the time complexity of KMP algorithm calculated?

suppose that the starting position of the N string is found in the M string, and the length is m and n, respectively. Using the KMP algorithm, it is generally believed that the time complexity is O (m), that is, the time complexity of calculating the next array is O (n), and the matching time is O (m),. But in the matching, it is assumed that I is used to identify the position in M, j is used to identify the position in N, and I is understandably increased but not decreased. But j will also backtrack according to the next array, and it may backtrack many times, so why is the time complexity of matching not O (masked n)? Solve

String-processing kmp

Mar.05,2021

the number of comparisons when calculating Partial_Table (or the list of longest common prefix suffixes of a pattern string) is between [mforce 2m], assuming the length of the pattern string at m.
the number of comparisons between pattern strings and substrings is between [n], and the worst case is T = "aaaabaaaab", P = "aaaaa".

so the time complexity of the algorithm is O (massin).

j backtracking, but forward

The backtracking of

j will only affect the upper and lower bounds of the number of search main cycles ([m, 2m]), not the relationship that makes it m _ n as you said.

you can understand that since m only increases but does not decrease, the worst-case scenario goes like this:

every match fails (m remains the same)

failed to match again (massi1)

in this case, each character in M is actually compared twice, so a total of 2m loops are executed. This is the upper limit of the number of cycles. In any other case, there are at least several cycles that are m direct + 1.

Previous: There are two navigation switches on the page, how to avoid gaps in the switch?

Next: How to solve the problem of infinite creation of scheduled tasks by django_celery_beat?