第四题字符串： 通过80%超时

n = 9
mo = "abaabaabaab"
m = 3
m_str = ["aba","ab","abaaba"]


n = len(mo)
next = [0 for i in range(n+1)]
def getnext(n2):
    i = 0
    j = -1
    while i<n2:
        if j==-1 or mo[i] == mo[j]:
            i+=1
            j+=1
            next[i] = j
        else:
            j = next[j]
next[0]=-1
getnext(len(mo))
xun = n - next[-1]
ans = 0
for i in range(m):
    m_s = m_str[i] #input
    f = 0
    for j in range(len(m_s)):
        if m_s[j] != mo[j]:
            f = 1
            break
    if f == 0 and len(m_s)%xun == 0:
        ans +=1

print(ans)