Hello, every one!
This lecture of data structure and algorithm is about KMP algorithm in the fourth chapter.
In the KMP algorithm, the main point is to reduce backtracking as possible as we can.
KMP is, in fact, an algorithm without backtracking.
Then which character pk in P should we use to continue to compare with ti when there is mismatch?
Knuth et al
found the value k only depending on the pattern itself
but not related to the target. Let us discuss the process.
For this target string and pattern string,
the result of their comparison are all equal at first,
but ti is not equal to pj.
If it is simple matching, it goes back to
ti-j+1 and continue to compare with p0. This is the matching process.
If we know ahead of time that
this string is not equal to this one. In fact,
they are real substring of the head and tail. That is, when we find they are not equal,
we will cover it. Then we will focus on the substring of the pattern P.
If they are not equal, there is no point for the next comparison, as we will soon find they are not equal.
Then let us go on. Here is this string.
The length of the string shortens by one.
But in fact we will slide to the right for two.
If they are still not equal, there is still no need to compare.
Until the k,
which means the length of the substring of its head and tail,
so that the substring of its head and tail are all equal for k characters correspondingly
In this case,
as they are equal for k characters and
the substring of p's tail has
been compared with target string just now, we then know
the p0 and the ti-k as well as pk-1 and the ti-1
are also equal correspondingly. As a result, we only need to
compare with pk and ti.
The whole pattern can slide to the right for j-k.
Then let us focus on the feature vector of the string.
In fact, it is a set of integers.
It is also called next array by some documents.
Let us look at the construction method. In fact,
it is to find out the longest one of
the substring of its head and tail before it.
In other special case, such as j=0, we stipulate it is equal to -1 just for convenience.
If we can not find out substrings like this, the k is 0.
Why should we find out the longest one?
Here is its characteristic value. The value at N=4
is originally equal to 3
according to the substring of its head and tail.
Now let it be 1. It is still right, as there are
matching substring for the length of 1.
However, if it is not the maximum value 3,
we will miss some match in some cases.
For example when we match this one and there is no match at P4
we will see,
because we give it as 1 but not the maximum one,
we will compare with P1
and the subscript 7 in the target string.
As a result, it is a very long slide, which is j minus k,
so it will slide for 3 when j=4 and k=1.
In fact, it should slide for 1, which is 4 minus 3, so we miss a probable match.
Let us look at the process of the KMP pattern match.
We find out the feature vector for this pattern.
When there is mismatch at a certain position,
we will look up the feature vector directly
and find out the k value.
This Pk will compare with Ti directly.
The match process is completed. It is very fast. Let us look at the KMP pattern match algorithm.
We assume it has provided with a feature vector and start at the 0 position of pattern and a specific start position of target.
The ij will move forward.
If the corresponding characters are equal,
i++, j++ we will compare for the next one.
When at a position
j==-1, in fact it is when next is 0.
So this one is not equal.
Then j+1 and this is equal to 0
then i+1. That is move forward for another one to continue.
There is also no backtracking. When there is mismatch, then the j is the next j in feature vector,
which is k.
The k value is less then j value.
The P, j and T, i continue to compare.
When this circulation is completed. If the j
is bigger than or equal to the length of the pattern, the match succeeds,
or the match fails. The algorithm to find out the feature vector
is a process of recursion. For n0, we stipulate
it is -1. We assume
we have worked out some positions, which are before j.
Assume we are nj, then it is equal to k.
We want to work out n j+1, that is,
this pj is not equal to pk.
Then let k equal to nk. When there is mismatch
we will continue to compare using the feature before it.
So it is also a process of KMP. So it works out a child feature vector
and use it to do the match.
until the condition ｕｍ is not satisfied which means pj equal to pk.
At this point, n j+1 is equal to k+1. For this feature vector,
the length plus one for the head and tail.
For the feature vector, we should deal with the special cases at first.
For j=1, we can work it out using this circulation.
For j=1, the feature vector value is equal to 0,
because there is no real substring.
For this value got by it,
the k value is consistent. If the P[j]
is not equal to P[k], we will use the k value
we have got before
to cover this k, k=next[k]. This must be smaller, because
k is smaller than next[k] and j is also smaller than next[j].
If they are equal, when j++, k++,
we will continue to compare. The length of the matching string plus one.
We let the value of next[j] equal to k.
In fact, it is the k plus one.
This is a demonstration to work out
the feature vector. In this process, it always covers itself
and looks at the head and tail of the substring.
For this feature value, it changes gradually and plus one at most.
If it drops down, it can drop down to 0
or to a value smaller than the 3 and the k value.
We look at the process to match the head and tail.
Is there still room for opitimization?
Let us have a look when Pj==Pk.
Because Pj==Pk and Pj is not equal to ti just now.
So as you can see, when you compare Pk with ti next time,
it is certain they are not equal. So this can be omitted.
For the case when they are not equal, we can record it in the feature array.
Let us look at the example.
The feature vector has been worked out. When there is mismatch at the P3,
according to the feature vector,
we use the K=0, that is the P[0].
The P[0] is also a and equal to P[3].
Obviously, those are not equal just now and these are still not equal. So this line
marked red is redundancy. We can optimize at this point.
If it is um, P[k]==P[j], we let the value of the next equal to next[k] directly.
Because j is bigger than k,
we are sure to get a smaller k value.
Then we have seen the difference of the non-optimized version and the optimized version.
In fact, we can work out the k like this,
the feature position of which is like this,namely the longest k.
The optimizing is to find out whether Pk==Pj.
If so, let next[j]=next[k].
On the whole, some positions of the optimized next array
are smaller than those of the non-optimized one.
As for the time efficiency of the KMP algorithm,
it looks like a double circulation.
In the circulation, the most important sentence is j=Next[j],
which can not be executed more than n.
Because j minus 1 when this is executed.
For the operation when j increases, there is only the j++.
If j=N[j] is executed more than n, the value of j will be much smaller
than -1.
In j becomes -1 only by accident and will soon be back to 0.
This is a dealing skill of the algorithm, so the process
is going up to O(n) and the KMP algorithm is to O(n).
The preprocess for the feature vector is also KMP.
So the time is to m.
So the whole time is n+m. Let us conclude about the efficiency.
The simple algorithm does not need preprocess.
But the time for matching is n*m.
For the KMP algorithm, the preprocess is to m
and the whole matching is to n.
Because it is the minimum. So it can be represented by theta in fact.
You can study other pattern matching algorithm if you are interested.
At last, leave this for you to think of.
There is different stipulation as well as different methods for calculating the feature vector.
The various methods fit various application.
We can compare and realize them.
Thank you!