fork download
copy 
  1. mod=10**9+7
  2. #import resource
  3. #resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
  4. import threading
  5. threading.stack_size(2**28)
  6. import sys
  7. sys.setrecursionlimit(10**6)
  8. #fact=[1]
  9. #for i in range(1,10001):
  10. #    fact.append((fact[-1]*i)%mod)
  11. #ifact=[0]*10001
  12. #ifact[10000]=pow(fact[10000],mod-2,mod)
  13. #for i in range(10000,0,-1):
  14. #    ifact[i-1]=(i*ifact[i])%mod
  15. from sys import stdin, stdout
  16. import bisect
  17. from bisect import bisect_left as bl              #c++ lowerbound bl(array,element)
  18. from bisect import bisect_right as br             #c++ upperbound
  19. import itertools
  20. import collections
  21. import math
  22. import heapq
  23. from random import randint as rn
  24. #from Queue import Queue as Q
  25. def modinv(n,p):
  26.     return pow(n,p-2,p)
  27. def ncr(n,r,p):                        #for using this uncomment the lines calculating fact and ifact
  28.     t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
  29.     return t
  30. def ain():                           #takes array as input
  31.     return list(map(int,sin().split()))
  32. def sin():
  33.     return input().strip()
  34. def GCD(x,y):
  35.     while(y):
  36.         x, y = y, x % y
  37.     return x
  38. class node:
  39.     def __init__(self,s,l,p):
  40.         self.child={}
  41.         self.se=s
  42.         self.le=l
  43.         self.parent=p
  44.         self.val=0
  45. """**************************************************************************"""
  46. def main():
  47.     def sufarr(s):
  48.         n=len(s)
  49.         o=[0]*n
  50.         o[0]=n-1
  51.         f=[0]*26
  52.         f[0]=1
  53.         for i in range(n-1):
  54.             f[ord(s[i])-65]+=1
  55.         for i in range(1,26):
  56.             f[i]+=f[i-1]
  57.         for i in range(n-2,-1,-1):
  58.             f[ord(s[i])-65]-=1
  59.             o[f[ord(s[i])-65]]=i
  60.         c=[0]*n
  61.         for i in range(1,n):
  62.             if(s[o[i]]==s[o[i-1]]):
  63.                 c[o[i]]=c[o[i-1]]
  64.             else:
  65.                 c[o[i]]=c[o[i-1]]+1
  66.         l=1
  67.         while(l<n):
  68.             f=[0]*n
  69.             for i in range(n):
  70.                 f[c[i]]+=1
  71.             for i in range(1,n):
  72.                 f[i]+=f[i-1]
  73.             od=[0]*n
  74.             for i in range(n-1,-1,-1):
  75.                 pt=(o[i]-l)%n
  76.                 f[c[pt]]-=1
  77.                 od[f[c[pt]]]=pt
  78.             cd=[0]*n
  79.             for i in range(1,n):
  80.                 x1=c[od[i]]
  81.                 y1=c[(od[i]+l)%n]
  82.                 x2=c[od[i-1]]
  83.                 y2=c[(od[i-1]+l)%n]
  84.                 if(x1==x2 and y1==y2):
  85.                     cd[od[i]]=cd[od[i-1]]
  86.                 else:
  87.                     cd[od[i]]=cd[od[i-1]]+1
  88.             o=od[::]
  89.             c=cd[::]
  90.             l*=2
  91.         return o
  92.     def LCP(o):
  93.         n=len(o)
  94.         poso=[0]*n
  95.         for i in range(n):
  96.             poso[o[i]]=i
  97.         lc=0
  98.         lcp=[0]*(n-1)
  99.         s=o[0]
  100.         for i in range(n):
  101.             oi=poso[s]
  102.             if(oi == n-1):
  103.                 lc=0
  104.                 s=(s+1)%n
  105.                 continue
  106.             ns=o[oi+1]
  107.             lc=lcpcal(s,ns,lc-1)
  108.             lcp[oi]=lc
  109.             s=(s+1)%n
  110.         return lcp
  111.     def lcpcal(i,j,k):
  112.         l=max(0,k)
  113.         while (i+l < len(st)) and (j+l < len(st)) :
  114.             if(st[i+l]==st[j+l]):
  115.                 l+=1
  116.             else:
  117.                 break
  118.         return l
  119.     def suftree():
  120.         a=node(-1,0,-1)
  121.         b=node(o[0],1,a)
  122.         a.child[st[o[0]]]=b
  123.         t=a
  124.         a=b
  125.         r=1
  126.         for i in range(1,n):
  127.             x=lcp[i-1]
  128.             y=o[i]
  129.             while(r>x):
  130.                 r-=a.le
  131.                 a=a.parent
  132.             if(r==x):
  133.                 b=node(y+x,n-(y+x),a)
  134.                 a.child[st[y+x]]=b
  135.                 cloc[o[i]]=b
  136.                 a=b
  137.             else:
  138.                 q=x-r
  139.                 k=a.child[st[y+r]]
  140.                 w1=node(k.se,q,a)
  141.                 w2=node(y+x,n-(x+y),w1)
  142.                 cloc[o[i]]=w2
  143.                 k.se=w1.se+q
  144.                 k.le-=q
  145.                 k.parent=w1
  146.                 w1.child[st[k.se]]=k
  147.                 w1.child[st[w2.se]]=w2
  148.                 del a.child[st[y+r]]
  149.                 a.child[st[w1.se]]=w1
  150.                 a=w2
  151.             r=n-y
  152.         return t
  153.     def dfs(x):
  154.         k[0]+=x.le
  155.         for i in x.child:
  156.             dfs(x.child[i])
  157.     q=int(sin())
  158.     b=[]
  159.     for i in range(q):
  160.         b.append(sin())
  161.     r=b[::-1]
  162.     r.append("$")
  163.     st="".join(r)
  164.     n=len(st)
  165.     o=sufarr(st)
  166.     lcp=LCP(o)
  167.     cloc=[0]*len(st)
  168.     t=suftree()
  169.     k=[-len(st)]
  170.     dfs(t)
  171.     k=k[0]
  172.     ans=[k]
  173.     j=0
  174.     for i in range(q-1):
  175.         x=len(r[i])
  176.         f=j+x
  177.         while(j<f):
  178.             y=cloc[j]
  179.             while(len(y.parent.child)==1):
  180.                 k-=y.le
  181.                 y=y.parent
  182.             k-=y.le
  183.             k+=1
  184.             a=st[y.se]
  185.             del y.parent.child[a]
  186.             j+=1
  187.         ans.append(k)
  188.     ans=map(str,ans[::-1])
  189.     print"\n".join(ans)
  190. ######## Python 2 and 3 footer by Pajenegod and c1729
  191. py2 = round(0.5)
  192. if py2:
  193.     from future_builtins import ascii, filter, hex, map, oct, zip
  194.     range = xrange
  195.  
  196. import os, sys
  197. from io import IOBase, BytesIO
  198.  
  199. BUFSIZE = 8192
  200. class FastIO(BytesIO):
  201.     newlines = 0
  202.     def __init__(self, file):
  203.         self._file = file
  204.         self._fd = file.fileno()
  205.         self.writable = "x" in file.mode or "w" in file.mode
  206.         self.write = super(FastIO, self).write if self.writable else None
  207.  
  208.     def _fill(self):
  209.         s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
  210.         self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
  211.         return s
  212.     def read(self):
  213.         while self._fill(): pass
  214.         return super(FastIO,self).read()
  215.  
  216.     def readline(self):
  217.         while self.newlines == 0:
  218.             s = self._fill(); self.newlines = s.count(b"\n") + (not s)
  219.         self.newlines -= 1
  220.         return super(FastIO, self).readline()
  221.  
  222.     def flush(self):
  223.         if self.writable:
  224.             os.write(self._fd, self.getvalue())
  225.             self.truncate(0), self.seek(0)
  226.  
  227. class IOWrapper(IOBase):
  228.     def __init__(self, file):
  229.         self.buffer = FastIO(file)
  230.         self.flush = self.buffer.flush
  231.         self.writable = self.buffer.writable
  232.         if py2:
  233.             self.write = self.buffer.write
  234.             self.read = self.buffer.read
  235.             self.readline = self.buffer.readline
  236.         else:
  237.             self.write = lambda s:self.buffer.write(s.encode('ascii'))
  238.             self.read = lambda:self.buffer.read().decode('ascii')
  239.             self.readline = lambda:self.buffer.readline().decode('ascii')
  240.  
  241. sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  242. input = lambda: sys.stdin.readline().rstrip('\r\n')
  243.  
  244. #if __name__ == '__main__':
  245. #   main()
  246. threading.Thread(target=main).start()
  247.  
Success #stdin #stdout #stderr 0.01s 10760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread Thread-1:
Traceback (most recent call last):
  File "/usr/lib/python2.7/threading.py", line 801, in __bootstrap_inner
    self.run()
  File "/usr/lib/python2.7/threading.py", line 754, in run
    self.__target(*self.__args, **self.__kwargs)
  File "prog.py", line 157, in main
ValueError: invalid literal for int() with base 10: ''
https://ideone.com/v0xAuf
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!