import re
import time

SS = str(13**100500)
print(len(SS))
SUB = '637036977498347229246'
TEMPLATE = "63@036@7749@347@29@46"

#time_start = time.monotonic()
#result = SS.find(SUB)
#time_end = time.monotonic()
#print(f"result: {result}, str search worktime: {1000 * (time_end - time_start):.3f}ms")


def check_pattern_3(s, template):
    m_shifts = []
    t_shift = 0
    for substr in template.split('@'):
        if substr:
            m_shifts.append((t_shift, substr))
        t_shift += len(substr) + 1

    # special cases
    if len(m_shifts) == 0:
        return 0 if len(template) <= len(s) else -1

    max_shift = len(s) - len(template)
    curr_shift = 0
    while curr_shift <= max_shift:
        next_shift = curr_shift
        for shift_substr, substr in m_shifts:
            next_shift = s.find(substr, next_shift + shift_substr) - shift_substr
            if next_shift < 0:
                return -1
        if next_shift == curr_shift:
            return curr_shift
        else:
            curr_shift = next_shift
    return -1


def check_pattern_re(s, template):
    res = re.findall(template.replace('@', '.'), s)
    return s.find(res[0]) if res else -1

def run_tests(func, name='no name'):
    is_fail = False
    test_cases = [
        ('', '', 0),
        ('0011223344', '', 0),
        ('0011223344', '@', 0),
        ('00', '@@', 0),
        ('00', '@@@', -1),
        ('0123', '0123', 0),
        ('0123', '@1', 0),
        ('0123', '@0', -1),
        ('0123', '@3', 2),
        ('0123', '@4', -1),
        ('0123', '@0@', -1),
        ('0123', '@1@', 0),
        ('0123', '@2@', 1),
        ('0123', '@3@', -1),
        ('0000111', '@0011@', 1),
        ('xxxaaabbbcccxxx', 'aa@bb@cc', 3),
        ('xxxaaabbbcccxxx', 'aa@bb@@cc', 3),
        ('xxxaaabbbcccxxx', 'aa@bb@@@cc', -1),
    ]
    for test_str, test_template, test_expected in test_cases:
        ret = func(test_str, test_template)
        if ret != test_expected:
            is_fail = True
            print(f"[{name}] Test fail", test_str, test_template, ret, test_expected)

    assert is_fail == False

run_tests(check_pattern_re, 'version re')
run_tests(check_pattern_3, 'version 3')

time_start = time.monotonic()
result = check_pattern_3(SS, TEMPLATE)
time_end = time.monotonic()

worktime = 1000 * (time_end - time_start)
print(f"result: {result}, worktime: {worktime:.3f}ms")