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**7)
  8. #fact=[1]
  9. #for i in range(1,1000001):
  10. #    fact.append((fact[-1]*i)%mod)
  11. #ifact=[0]*1000001
  12. #ifact[1000000]=pow(fact[1000000],mod-2,mod)
  13. #for i in range(1000000,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.                 a=b
  136.             else:
  137.                 q=x-r
  138.                 k=a.child[st[y+r]]
  139.                 w1=node(k.se,q,a)
  140.                 w2=node(y+x,n-(x+y),w1)
  141.                 k.se=w1.se+q
  142.                 k.le-=q
  143.                 k.parent=w1
  144.                 w1.child[st[k.se]]=k
  145.                 w1.child[st[w2.se]]=w2
  146.                 del a.child[st[y+r]]
  147.                 a.child[st[w1.se]]=w1
  148.                 a=w2
  149.             r=n-y
  150.         return t
  151.     def dfs(x):
  152.         if(len(x.child)==0):
  153.             x.val=x.le-1
  154.         else:
  155.             x.val=x.le
  156.         for i in x.child:
  157.             x.val+=dfs(x.child[i])
  158.         return x.val
  159.     st=list(sin())
  160.     st.append("$")
  161.     x=int(sin())
  162.     q1=list(map(str,sin().split()))
  163.     q2=list(map(int,sin().split()))
  164.     n=len(st)
  165.     o=sufarr(st)
  166.     lcp=LCP(o)
  167.     t=suftree()
  168.     dfs(t)
  169.     f=[]
  170.     for i in range(x):
  171.         b=t
  172.         k=q2[i]
  173.         s=q1[i]
  174.         j=0
  175.         t2=0
  176.         while(b.val>k and j<len(s)):
  177.             if((b.val-b.le+1)<=k):
  178.                 j+=b.val-k+1
  179.                 break
  180.             else:
  181.                 j+=b.le
  182.             if(j>=len(s)):
  183.                 t2=1
  184.                 break
  185.             b=b.child[s[j]]
  186.             if(b.val<=k):
  187.                 j+=1
  188.                 break
  189.         if(j<=len(s) and t2==0):
  190.             print j,
  191.         else:
  192.             print "-1",
  193. ######## Python 2 and 3 footer by Pajenegod and c1729
  194. py2 = round(0.5)
  195. if py2:
  196.     from future_builtins import ascii, filter, hex, map, oct, zip
  197.     range = xrange
  198.  
  199. import os, sys
  200. from io import IOBase, BytesIO
  201.  
  202. BUFSIZE = 8192
  203. class FastIO(BytesIO):
  204.     newlines = 0
  205.     def __init__(self, file):
  206.         self._file = file
  207.         self._fd = file.fileno()
  208.         self.writable = "x" in file.mode or "w" in file.mode
  209.         self.write = super(FastIO, self).write if self.writable else None
  210.  
  211.     def _fill(self):
  212.         s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
  213.         self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
  214.         return s
  215.     def read(self):
  216.         while self._fill(): pass
  217.         return super(FastIO,self).read()
  218.  
  219.     def readline(self):
  220.         while self.newlines == 0:
  221.             s = self._fill(); self.newlines = s.count(b"\n") + (not s)
  222.         self.newlines -= 1
  223.         return super(FastIO, self).readline()
  224.  
  225.     def flush(self):
  226.         if self.writable:
  227.             os.write(self._fd, self.getvalue())
  228.             self.truncate(0), self.seek(0)
  229.  
  230. class IOWrapper(IOBase):
  231.     def __init__(self, file):
  232.         self.buffer = FastIO(file)
  233.         self.flush = self.buffer.flush
  234.         self.writable = self.buffer.writable
  235.         if py2:
  236.             self.write = self.buffer.write
  237.             self.read = self.buffer.read
  238.             self.readline = self.buffer.readline
  239.         else:
  240.             self.write = lambda s:self.buffer.write(s.encode('ascii'))
  241.             self.read = lambda:self.buffer.read().decode('ascii')
  242.             self.readline = lambda:self.buffer.readline().decode('ascii')
  243.  
  244. sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
  245. input = lambda: sys.stdin.readline().rstrip('\r\n')
  246.  
  247. #if __name__ == '__main__':
  248. #   main()
  249. threading.Thread(target=main).start()
  250.  
Success #stdin #stdout #stderr 0.01s 10720KB
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 161, in main
ValueError: invalid literal for int() with base 10: ''
https://ideone.com/Bg6gw6
language:
Python (cpython 2.7.16)
created:
5 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!