- Notifications
You must be signed in to change notification settings - Fork 625
/
Copy pathlcp.py
42 lines (30 loc) · 889 Bytes
/
lcp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
fromsuffix_arrayimportSuffixArray
classLCP(object):
def__init__(self, s):
self.s=s
self.lcp_array= []
self.suffix_array=SuffixArray(s)
self.suffix_array.create_suffix_array()
deflcp_w_suffix_str(self):
N=len(self.suffix_array.suffix_array)
array=self.suffix_array.suffix_array
self.lcp_array= [0]*N
inv_suffix= [0]*N
forindexinrange(N):
inv_suffix[array[index].index] =index
maxLen=0
forindexinrange(N):
ifinv_suffix[index] ==N-1:
maxLen=0
continue
index_j=array[inv_suffix[index]+1].index
while(index+maxLen<Nandindex_j+maxLen<Nandself.s[index+maxLen] ==self.s[index_j+maxLen]):
maxLen+=1
self.lcp_array[inv_suffix[index]] =maxLen
ifmaxLen>0:
maxLen-=1
returnself.lcp_array
if__name__=='__main__':
lcp=LCP("banana")
lcp.lcp_w_suffix_str()
printlcp.lcp_array
