def KMP_Preprocessing(pattern, nSize):
pi = [0] * (nSize + 1)
k = -1
j = 0
pi[j] = k
while ( j < nSize ):
if ( k == -1 or pattern[j] == pattern[k] ):
j += 1
k += 1
pi[j] = k
else:
k = pi[k]
return pi
def KMP_find(text, pattern, ppi):
nSize = len(text)
nPSize = len(pattern)
i = 0
j = 0
while (i < nSize):
if ( j == -1 or text[i] == pattern[j] ):
i += 1
j += 1
else:
j = ppi[j];
if (j == nPSize):
print i-j
j = ppi[j];
strPattern = "ababababca"
strPattern_pi = KMP_Preprocessing(strPattern, len(strPattern) )
strString ="asdsadf9alkjababababcaasdf"
KMP_find(strString, strPattern, strPattern_pi)
'Coding > Python 삽질기' 카테고리의 다른 글
fibonacci 수열 (0) | 2013.06.20 |
---|---|
10000개의 겹치는 않는 좌표 만들기 (0) | 2012.11.07 |
[Python] Undo / Redo 구현하기 (0) | 2011.06.16 |