fork download 
  1. import re
  2. import time
  3.  
  4. SS = str(13**100500)
  5. print(len(SS))
  6. SUB = '637036977498347229246'
  7. TEMPLATE = "63@036@7749@347@29@46"
  8.  
  9. #time_start = time.monotonic()
  10. #result = SS.find(SUB)
  11. #time_end = time.monotonic()
  12. #print(f"result: {result}, str search worktime: {1000 * (time_end - time_start):.3f}ms")
  13.  
  14.  
  15. def check_pattern_3(s, template):
  16.     m_shifts = []
  17.     t_shift = 0
  18.     for substr in template.split('@'):
  19.         if substr:
  20.             m_shifts.append((t_shift, substr))
  21.         t_shift += len(substr) + 1
  22.  
  23.     # special cases
  24.     if len(m_shifts) == 0:
  25.         return 0 if len(template) <= len(s) else -1
  26.  
  27.     max_shift = len(s) - len(template)
  28.     curr_shift = 0
  29.     while curr_shift <= max_shift:
  30.         next_shift = curr_shift
  31.         for shift_substr, substr in m_shifts:
  32.             next_shift = s.find(substr, next_shift + shift_substr) - shift_substr
  33.             if next_shift < 0:
  34.                 return -1
  35.         if next_shift == curr_shift:
  36.             return curr_shift
  37.         else:
  38.             curr_shift = next_shift
  39.     return -1
  40.  
  41.  
  42. def check_pattern_re(s, template):
  43.     res = re.findall(template.replace('@', '.'), s)
  44.     return s.find(res[0]) if res else -1
  45.  
  46. def run_tests(func, name='no name'):
  47.     is_fail = False
  48.     test_cases = [
  49.         ('', '', 0),
  50.         ('0011223344', '', 0),
  51.         ('0011223344', '@', 0),
  52.         ('00', '@@', 0),
  53.         ('00', '@@@', -1),
  54.         ('0123', '0123', 0),
  55.         ('0123', '@1', 0),
  56.         ('0123', '@0', -1),
  57.         ('0123', '@3', 2),
  58.         ('0123', '@4', -1),
  59.         ('0123', '@0@', -1),
  60.         ('0123', '@1@', 0),
  61.         ('0123', '@2@', 1),
  62.         ('0123', '@3@', -1),
  63.         ('0000111', '@0011@', 1),
  64.         ('xxxaaabbbcccxxx', 'aa@bb@cc', 3),
  65.         ('xxxaaabbbcccxxx', 'aa@bb@@cc', 3),
  66.         ('xxxaaabbbcccxxx', 'aa@bb@@@cc', -1),
  67.     ]
  68.     for test_str, test_template, test_expected in test_cases:
  69.         ret = func(test_str, test_template)
  70.         if ret != test_expected:
  71.             is_fail = True
  72.             print(f"[{name}] Test fail", test_str, test_template, ret, test_expected)
  73.  
  74.     assert is_fail == False
  75.  
  76. run_tests(check_pattern_re, 'version re')
  77. run_tests(check_pattern_3, 'version 3')
  78.  
  79. time_start = time.monotonic()
  80. result = check_pattern_3(SS, TEMPLATE)
  81. time_end = time.monotonic()
  82.  
  83. worktime = 1000 * (time_end - time_start)
  84. print(f"result: {result}, worktime: {worktime:.3f}ms")
  85.  
Success #stdin #stdout 0.18s 9664KB
comments (?)
stdin 
Standard input is empty
stdout 
111952
result: 110890, worktime: 0.189ms
https://ideone.com/g6YGpn
language:
Python 3 nbc (python 3.7.3)
created:
3 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!