1. 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.
2. 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

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:

1. every match fails (m remains the same)
2. 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.