Реализации алгоритмов/Алгоритм Кнута — Морриса — Пратта: различия между версиями
Содержимое удалено Содержимое добавлено
РоманСузи (обсуждение | вклад) добавил из анлгичких wikibooks |
|||
Строка 243:
</source>
== Go ==
<source lang="go">
func computeLPS(pat string) (lps []int) {
M := len(pat)
lps = make([]int, M) // lps[0] = 0
l := 0 // length of the previous longest prefix suffix
// the loop calculates lps[i] for i = 1 to M-1
for i := 1; i < M; i++ {
for {
if pat[i] == pat[l] {
l++
break
}
if l == 0 {
break
}
l = lps[l-1]
}
lps[i] = l
}
return lps
}
func KMPSearch(pat, txt string) {
M, N := len(pat), len(txt)
// Preprocess the pattern that will hold the longest prefix suffix values for pattern
lps := computeLPS(pat)
for i, j := 0, 0; i < N; i++ {
for {
if pat[j] == txt[i] {
j++
if j == M {
fmt.Printf("Found pattern at index %d \n", i-j+1)
j = lps[j-1]
}
break
}
if j > 0 {
j = lps[j-1]
} else {
break
}
}
}
}
</source>
== Lua ==
Для Lua версии 5.1 и выше.
<source lang="lua">
-- Implementation of the Knuth Morris Pratt algorithm to find
-- substrings within strings.
-- Sean Brewer
-- Berry College CS 320
-- March 25, 2008
-- Generate the failure table using the substring and the length
-- of the substring
function generate_fail_table(substring,sublen)
comparisons = 0
fail = {0}
for i=2,sublen do
temp = fail[i - 1]
while temp > 0 and string.sub(substring,temp,temp) ~= string.sub(substring,i - 1,i - 1) do
comparisons = comparisons + 1
temp = fail[temp]
end
fail[i] = temp + 1
end
return {fail, comparisons + 1}
end
--The actual kmp algorithm which takes
--the substring and text as arguments
function kmp_algorithm(substring,text)
--starting positions...
subloc = 1
textloc = 1
--get the length of substring and text..
sublen = string.len(substring)
textlen = string.len(text)
--generate the fail links...
failure = generate_fail_table(substring,sublen)
--store failure comparisons
comparisons = failure[2]
--store fail table
fail = failure[1]
--the main loop..
while textloc <= textlen and subloc <= sublen do
if subloc == 0 or string.sub(text,textloc,textloc) == string.sub(substring,subloc,subloc) then
comparisons = comparisons + 1
textloc = textloc + 1
subloc = subloc + 1
else --no match found so follow fail link
subloc = fail[subloc]
end
end
if subloc > sublen then
return {textloc - sublen, comparisons}
else
return {0, comparisons}
end
end
</source>
== Python ==
<source lang="python">
# Knuth-Morris-Pratt string matching
# David Eppstein, UC Irvine, 1 Mar 2002
#from http://code.activestate.com/recipes/117214/
def KnuthMorrisPratt(text, pattern):
'''Yields all starting positions of copies of the pattern in the text.
Calling conventions are similar to string.find, but its arguments can be
lists or iterators, not just strings, it returns all matches, not just
the first one, and it does not need the whole text in memory at once.
Whenever it yields, it will have read the text exactly up to and including
the match that caused the yield.'''
# allow indexing into pattern and protect against change during yield
pattern = list(pattern)
# build table of shift amounts
shifts = [1] * (len(pattern) + 1)
shift = 1
for pos in range(len(pattern)):
while shift <= pos and pattern[pos] != pattern[pos-shift]:
shift += shifts[pos-shift]
shifts[pos+1] = shift
# do the actual search
startPos = 0
matchLen = 0
for c in text:
while matchLen == len(pattern) or \
matchLen >= 0 and pattern[matchLen] != c:
startPos += shifts[matchLen]
matchLen -= shifts[matchLen]
matchLen += 1
if matchLen == len(pattern):
yield startPos
</source>
{{translate}}
{{BookCat}}
| |||