fork download
copy 
  1. import sys
  2. sys.setrecursionlimit(10**6)
  3. class node:
  4.     def __init__(self,s,l,p):
  5.         self.child={}
  6.         self.se=s
  7.         self.le=l
  8.         self.parent=p
  9.         self.val=0
  10. def sufarr(s):
  11.     n=len(s)
  12.     o=[0]*n
  13.     o[0]=n-1
  14.     f=[0]*26
  15.     f[0]=1
  16.     for i in range(n-1):
  17.         f[ord(s[i])-65]+=1
  18.     for i in range(1,26):
  19.         f[i]+=f[i-1]
  20.     for i in range(n-2,-1,-1):
  21.         f[ord(s[i])-65]-=1
  22.         o[f[ord(s[i])-65]]=i
  23.     c=[0]*n
  24.     for i in range(1,n):
  25.         if(s[o[i]]==s[o[i-1]]):
  26.             c[o[i]]=c[o[i-1]]
  27.         else:
  28.             c[o[i]]=c[o[i-1]]+1
  29.     l=1
  30.     while(l<n):
  31.         f=[0]*n
  32.         for i in range(n):
  33.             f[c[i]]+=1
  34.         for i in range(1,n):
  35.             f[i]+=f[i-1]
  36.         od=[0]*n
  37.         for i in range(n-1,-1,-1):
  38.             pt=(o[i]-l)%n
  39.             f[c[pt]]-=1
  40.             od[f[c[pt]]]=pt
  41.         cd=[0]*n
  42.         for i in range(1,n):
  43.             x1=c[od[i]]
  44.             y1=c[(od[i]+l)%n]
  45.             x2=c[od[i-1]]
  46.             y2=c[(od[i-1]+l)%n]
  47.             if(x1==x2 and y1==y2):
  48.                 cd[od[i]]=cd[od[i-1]]
  49.             else:
  50.                 cd[od[i]]=cd[od[i-1]]+1
  51.         o=od[::]
  52.         c=cd[::]
  53.         l*=2
  54.     return o
  55. def LCP(o):
  56.     n=len(o)
  57.     poso=[0]*n
  58.     for i in range(n):
  59.         poso[o[i]]=i
  60.     lc=0
  61.     lcp=[0]*(n-1)
  62.     s=o[0]
  63.     for i in range(n):
  64.         oi=poso[s]
  65.         if(oi == n-1):
  66.             lc=0
  67.             s=(s+1)%n
  68.             continue
  69.         ns=o[oi+1]
  70.         lc=lcpcal(s,ns,lc-1)
  71.         lcp[oi]=lc
  72.         s=(s+1)%n
  73.     return lcp
  74. def lcpcal(i,j,k):
  75.     l=max(0,k)
  76.     while (i+l < len(st)) and (j+l < len(st)) :
  77.         if(st[i+l]==st[j+l]):
  78.             l+=1
  79.         else:
  80.             break
  81.     return l
  82. def suftree():
  83.     a=node(-1,0,-1)
  84.     b=node(o[0],1,a)
  85.     a.child[st[o[0]]]=b
  86.     t=a
  87.     a=b
  88.     r=1
  89.     for i in range(1,n):
  90.         x=lcp[i-1]
  91.         y=o[i]
  92.         while(r>x):
  93.             r-=a.le
  94.             a=a.parent
  95.         if(r==x):
  96.             b=node(y+x,n-(y+x),a)
  97.             a.child[st[y+x]]=b
  98.             a=b
  99.         else:
  100.             q=x-r
  101.             k=a.child[st[y+r]]
  102.             w1=node(k.se,q,a)
  103.             w2=node(y+x,n-(x+y),w1)
  104.             k.se=w1.se+q
  105.             k.le-=q
  106.             k.parent=w1
  107.             w1.child[st[k.se]]=k
  108.             w1.child[st[w2.se]]=w2
  109.             del a.child[st[y+r]]
  110.             a.child[st[w1.se]]=w1
  111.             a=w2
  112.         r=n-y
  113.     return t
  114. def dfs(x):
  115.     if(len(x.child)==0):
  116.         x.val=x.le-1
  117.     else:
  118.         x.val=x.le
  119.     for i in x.child:
  120.         x.val+=dfs(x.child[i])
  121.     return x.val
  122. st=list(raw_input())
  123. st.append("$")
  124. n=len(st)
  125. o=sufarr(st)
  126. lcp=LCP(o)
  127. t=suftree() #t stores the address of root node of the suffix tree
  128.  
Runtime error #stdin #stdout #stderr 0.01s 7208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 122, in <module>
EOFError: EOF when reading a line
https://ideone.com/7PWvv7
language:
Python (cpython 2.7.16)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!