Knuth-Morris-Pratt算法（KMP）Fast pattern matching in strings
需积分: 44 185 浏览量
2014-01-14
16:02:43
上传
评论 2
收藏 2.97MB PDF 举报
SIAM
J.
COMPUT.
Vol.
6,
No.
2,
June
1977
FAST
PATTERN
MATCHING
IN
STRINGS*
DONALD
E.
KNUTHf,
JAMES
H.
MORRIS,
JR.:l:
AND
VAUGHAN
R.
PRATT
Abstract.
An
algorithm
is
presented
which
finds
all
occurrences
of
one.
given
string
within
another,
in
running
time
proportional
to
the
sum
of
the
lengths
of
the
strings.
The
constant
of
proportionality
is
low
enough
to
make
this
algorithm
of
practical
use,
and
the
procedure
can
also
be
extended
to
deal
with
some
more
general
pattern-matching
problems.
A
theoretical
application
of
the
algorithm
shows
that
the
set
of
concatenations
of
even
palindromes,
i.e.,
the
language
{can}
*,
can
be
recognized
in
linear
time.
Other
algorithms
which
run
even
faster
on
the
average
are
also
considered.
Key
words,
pattern,
string,
text-editing,
pattern-matching,
trie
memory,
searching,
period
of
a
string,
palindrome,
optimum
algorithm,
Fibonacci
string,
regular
expression
Text-editing
programs
are
often
required
to
search
through
a
string
of
characters
looking
for
instances
of
a
given
"pattern"
string;
we
wish
to
find
all
positions,
or
perhaps
only
the
leftmost
position,
in
which
the
pattern
occurs
as
a
contiguous
substring
of
the
text.
For
example,
c
a
e
n
a
r
y
contains
the
pattern
e
n,
but
we
do
not
regard
c
a
n
a
r
y
as
a
substring.
The
obvious
way
to
search
for
a
matching
pattern
is
to
try
searching
at
every
starting
position
of
the
text,
abandoning
the
search
as
soon
as
an
incorrect
character
is
found.
But
this
approach
can
be
very
inefficient,
for
example
when
we
are
looking
for
an
occurrence
of
aaaaaaab
in
aaaaaaaaaaaaaab.
When
the
pattern
is
a"b
and
the
text
is
a2"b,
we
will
find
ourselves
making
(n
+
1)
comparisons
of
characters.
Furthermore,
the
traditional
approach
involves
"backing
up"
the
input
text
as
we
go
through
it,
and
this
can
add
annoying
complications
when
we
consider
the
buffering
operations
that
are
frequently
involved.
In
this
paper
we
describe
a
pattern-matching
algorithm
which
finds
all
occurrences
of
a
pattern
of
length
rn
within
a
text
of
length
n
in
O(rn
+
n)
units
of
time,
without
"backing
up"
the
input
text.
The
algorithm
needs
only
O(m)
locations
of
internal
memory
if
the
text
is
read
from
an
external
file,
and
only
O(log
m)
units
of
time
elapse
between
consecutive
single-character
inputs.
All
of
the
constants
of
proportionality
implied
by
these
"O"
formulas
are
independent
of
the
alphabet
size.
*
Received
by
the
editors
August
29,
1974,
and
in
revised
form
April
7,
1976.
t
Computer
Science
Department,
Stanford
University,
Stanford,
California
94305.
The
work
of
this
author
was
supported
in
part
by
the
National
Science
Foundation
under
Grant
GJ
36473X
and
by
the
Office
of
Naval
Research
under
Contract
NR
044-402.
Xerox
Palo
Alto
Research
Center,
Palo
Alto,
California
94304.
The
work
of
this
author
was
supported
in
part
by
the
National
Science
Foundation
under
Grant
GP
7635
at
the
University
of
California,
Berkeley.
Artificial
Intelligence
Laboratory,
Massachusetts
Institute
of
Technology,
Cambridge,
Mas-
sachusetts
02139.
The
work
of
this
author
was
supported
in
part
by
the
National
Science
Foundation
under
Grant
GP-6945
at
University
of
California,
Berkeley,
and
under
Grant
GJ-992
at
Stanford
University.
323
剩余27页未读，继续阅读
评论0
最新资源