1423. Басня о строке

1423.py

import io
import sys


def prefix(s):
    v = [0] * len(s)
    for i in range(1, len(s)):
        k = v[i - 1]
        while k > 0 and s[k] != s[i]:
            k = v[k - 1]
        if s[k] == s[i]:
            k += 1
        v[i] = k
    return v


def kmp(s, t):
    index = -1
    f = prefix(s)
    k = 0
    for i in range(len(t)):
        while k > 0 and s[k] != t[i]:
            k = f[k - 1]
        if s[k] == t[i]:
            k += 1
        if k == len(s):
            index = i - len(s) + 1
            break
    return index

input_stream = io.TextIOWrapper(sys.stdin.buffer, encoding='cp866')
n = int(input_stream.readline())
s = input_stream.read(n)
input_stream.readline()
t = input_stream.read(n)

s += s
i = kmp(t, s)
if i == -1:
    print(-1)
elif i == 0:
    print(0)
else:
    print(n - i)