Hello,
for this lecture of Data Structure and Algorithm,
we continue the study of chapter 4
Character String
we introduce a naive match algorithm
The pattern match of string
is a basic operation
in many applications.
For example, in a text editor,
we want to search a string.
Then I delete this string
or replace it with another string
In the target T,
we find a match string of pattern P
that is, find a continuous m characters
from a certain subscript i in T.
It is equal to P
at corresponding position.
Then we say
pattern P and target T are matched.
Our target is
in the target string,
find the start position
of our match string.
If we can find a reasonable position
then we succeed.
If we do not after a round,
we fail to match.
To solve suach a match problem.
We mainly have two algorithms.
The first is the naive algorithm.
it is a method of exhaustion in fact.
There is another non-backtrace
fast pattern match method.
For example, KMP.
Let us see an example of naive pattern match.
I imagin the target T
if from t0 to tn-1.
P is from p0 to pm-1.
Their subscripts are i and j respectively.
If we have a successful match,
that is from this i
we get p0=ti
until pm-1
equal to ti+m-1
that is, in t,
from i
we get a continuous substring of m
equal to
the match string.
If the match fails,
that is, from i
the continuous m characters
this substring
is not equal to p
Then at this time
we let the position i
of the target string T
to the next position to compare.
If we draw a picture
we let the pattern string p
move to the right by one
and compare with t
in corresponding position
Let us see an example of naive match
The pattern match is aaaa
until the last one is b
Our target string
is in such a form.
When they are not equal
we move p to the right
and align with t
to compare
until the last position.
If they are equal
we succeed.
Let us see another example,
it is also to move p to the right by one
when they are unequal
and align with t to continue
In fact, let us observe this pattern string.
it is a reprtition of abab
You can feel that
the second comparison
is unnecessary.
The next po and p1
this position
are a and b respectly.
It is not equal.
Obviously, it is not equal at the position of t1
so this is a redundancy comparison.
Let us see another example.
This pattern string abcdef f
As you see,
they are almost not equal at all in the front
But it and the target string
in corresponding position
are basically equal.
Only the last position are not equal.
In this unequal position,
we continue to match.
I still move the pattern
to the right by one each time.
and continue to compare.
The pattern string seems without law.
But it implies
an important law
This p
are not equal
in corresponding position.
It and the target string t
in corresponding position
are equal
When we compare later
you cam imagin,
it is meaningless comparison
There is no need.
We have known in advance
they can not be equal.
But in the naive method,
I can only
do it exhaustively.
Let us see the implementation of naive match method
First, the target string s
and the pattern string p
the start comparison position in s
is startindex.
I first calculate what the length of s minus p
equals to
This value is
in s
the right most position
that the substring can start at
If this value
LastIndex is smaller than startindex
we can not find
a substring with suit length
then I return -1
Otherwise, I let the subscript g
start with startindex
until Lastindex
I add 1 to g each time
and do corresponding operation
I start at g
and take the length
of the pattern string p
such a substring
After that,
I compare with p.
If they are equal
then I return
the start position subscript g
If I get out of this cycle,
and have not found
such a suit g
that is, the match fails
we return -1
Let see the second algorithm
of naive match.
Essentially it is the same as
the first one.
The way of writing is different.
Let the subscript i
be the start position in the target string
and the subscript j
be 0 of the pattern string
as the start position
When i and j
are both in reasonable string scope
that is, i is smaller than target string
j is smaller than pattern string
Let us make sure whether
p[j] and t[i] are equal.
If so,
we add 1 to them respectively
and continue to the next position.
If not,
in this case,
we let the subscript i of the target string
return to the next position
of that there is the comparison
The subscript of the pattern
returns to 0
Out of this cycle.
if j>=p.length()
I can make sure at this place,
j==p.length()
means that the pattern string p
succeed in reaching
such an end position of \0
In fact, this is a match string
of the target string.
we return i-j
such a position of start subscript
This substring is found.
Otherwise, if I get out of the cycle,
j is smaller than p.length()
it means that I can not continue to compare.
But at this time, in the pattern string,
the subscript j
has not reached the end.
That is, the match fails.
Let us see another simplier writing method.
It is still a naive
pattern match method.
The arguments passed in is similar.
I let the subscript g
from the start position of
the target string
When g is smaller than the length of target string
minus the pattern string.
Let g does an operation one by one
In that cycle, I let the subscript
of p be j
When j
is smaller than p.length()
that is in its scope
and in t
the start g plus j
is current position
If it is equal to
the j position of pattern p.
I let j ++
and continue to compare.
It I get out of this inner loop,
j happens to be equal
to the length of pattern p
It means the match succeeds.
I can return directly.
If not
and g
is still
in the legal subscript scope
I let g
be the next position of
the start position just now
I continue this comparison.
If I get out of this loop,
and can not find a suit start position g
The match fails.
-1 is returned
Let us see the efficiency
of naive match
Imagine the length of target T
is n
and the length of pattern p is m
OF course m is smaller than or equal to n
In the worst case,
the surrounding loop
fails every time
the probable start position
travels the position
from 0 to n-m
in the inner loop,
that is p and t compare
at corresponding position
Suppose that I do not find they are unequal
until the last position.
This inner layer
will compare for m times.
Then it
will be O(m×n) times in total
so many operations.
Let us see an example,
in the worst case,
the target a repeats n-1 times
and end with x
the pattern string is a repeat m-1 times
and end with b
In the case with success,
we continue to the last position
and x is equal to b.
As you see, the surrounding loop
cycles n-m+1
the inner loop cycles m times each time.
The time complexity in total
is O（m×n）
In the case of failure
Suppose x is c
it is similar
the surronding loop is n-m+1 times
and inner m times
still O(m×n)
Let us see the best situation
for naive match method.
In the case of successful match
I find the pattern string
in the m position in the front.
In this case,
I only need search
of O（m） times
and find it.
In case of failure,
I find
mismatch
at the first position of this pattern
So the inner loop needs
only one
But the surrounding loop
needs n-m+1
In total
the time complexity
is O（n）
At last, leave you some questions.
the naive match method
inefficient
because there is
some redundancy comparison.
Let us imagine such examples.
We can see the redundancy phenomenon.
You can design some other examples.
You can see
why this redundancy appears?
Can we
design a more reasonable algorithm.
to eliminate it.
so that let the subscript of
target t not trace back as possible as you can
when doing the match
That is, I will not go back to the start point
at one blow.
Some comparison in-between
can be omitted
Thank you.