fork download
copy 
  1. import sys
  2.  
  3.  
  4. def z_function(string, z, lenth):
  5.  
  6.     left = 0
  7.     right = 0
  8.  
  9.     for i in xrange(1, lenth):
  10.         if i <= right:
  11.              z[i] = min(z[i - left], right - i + 1)
  12.         while i + z[i] < lenth and string[z[i]] == string[i + z[i]]:
  13.             z[i] += 1
  14.         if i + z[i] - 1 > right:
  15.             right = i + z[i] - 1
  16.             left = i
  17.  
  18.  
  19. def main():
  20.     flag = 0
  21.  
  22.     for line in sys.stdin:
  23.         if flag == 0:
  24.             n = int(line.strip())
  25.             flag = 1
  26.             continue
  27.         elif flag == 1:
  28.             needle = line.strip()
  29.             flag = 2
  30.             continue
  31.         else:
  32.             haystack = line.strip()
  33.             flag = 0
  34.  
  35.         string = needle + '&' + haystack
  36.  
  37.         lenth = len(string)
  38.         z = [0] * lenth
  39.         z_function(string, z, lenth)
  40.         s = 0
  41.         for i in xrange(n + 1, lenth - n + 1):
  42.             if z[i] == n:
  43.                 s = 1
  44.                 print i - n - 1
  45.         if s == 1:
  46.             sys.stdout.write("\n\n")
  47.  
  48. if __name__ == "__main__":
  49.     main()
Success #stdin #stdout 0.01s 8976KB
comments (?)
stdin
copy 
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo
stdout
copy 
2
4


3
9
15
21
https://ideone.com/unZkp1
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
secret

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!