KMP: Match a non-retractable algorithm for a short sub-string in a long string.
Let's take a look at the most "simple" algorithm. Of course, the program is written here. I can understand the skill of this original master:
/// Find A Template in a string.
INT INDEX (Char * S, Char * T, INT POS)
{
INT i = POS, J = 1;
While (i <= s [0] && j <= t [0])
{
IF (s [i] == t [j]) { i; J;} // If the same, continue to compare
Else {i = i-j 2; j = 1;} // If there is different, backtrack, re-find
}
IF (j> t [0]) Return I-T [0];
Else Return 0;
}
It should be noted that the first byte of the two strings here is stored in the length of the string, so no matter in any case, don't forget, this way of writing can only match the longest 255 string. I hope that more than a longer string, please replace the type yourself. Or simply pass the parameters of 2 SIZE_T.
The KMP algorithm is analyzed by analyzing the substrings. When calculating each location does not match, the next comparison position of the desired GOT is sorted out, and then uses it in the algorithm above. (Who knows, huh, huh, there is a reward here)
Explain:
When we analyze a substring, for example: abcabcddes. You need to analyze, and how many characters and strings in front of each character match the character starting from the initial position. Then 1, don't forget, our strings start from index 1) Of course, do not match themselves, the default first character is 0.
For example, as follows:
Abcabcddes
0111234111
^ ------------------- default is 0
^^^ ---------------- Can not match the same characters, so the person can think that it is not yes 0 1 = 1
^^^ ------------ The characters in the previous character are the same, so it is 2, 3, 4
^^^ ------- Matching can only be taken.
I hope I can understand that if the start character is CH1, then we have to start the next position behind the second CH1 in the string, and calculate the maximum energeticity.
The program is written here:
Void getNext (Char * t, int * Next)
{
INT i = 1, j = 0; Next [1] = 0;
While (i IF (j == 0 || T [i] == t [j]) { i; J; NEXT [I] = j; } Else J = Next [J]; } } But this is not the best because he did not consider the situation in Aaaaaaaaaaaaaaaab, so that a large number of 1 in front will have, such algorithm complexity has nothing to distinguish. So change slightly: Void getNextex (char * t, char * next) { INT i = 1, j = 0; Next [1] = 0; While (i { IF (j == 0 || T [i] == t [j]) { i; J; IF (t [i] == t [j]) Next [i] = next [j]; Else NEXT [I] = j; } Else J = Next [J]; } } Now we can get the value of this next string, the next is the body of the KMP algorithm: Quite simple: INT KMP (Char * S, Char * T, INT POS) { INT i = POS, J = 1; While (i { IF (s [i] == t [j]) { i; j;} Else J = Next [J] } IF (j> t [0]) Return I-T [0]; Else Return 0; } Compared with the simple algorithm, just modify one sentence, but the algorithm complexity is turned from O (M * n): o (m) Thanks to the great algorithm master's wonderful algorithm, and the teacher's rigorous attitude. Chaos
