Leetcode 1071. Greatest Common Divisor of Strings [Python]_1071. greatest common divisor of strings python

开始想复杂了点。想用KMP，不过只知道基础版本的KMP能找Pattern串重复的开始位置。可以从最长Pattern的长度入手。其最长为Str2的长度（== Str2），所以可以从len(Str2)长度往回遍历。找到可以被Str1和Str2长度整除的Pattern长度，然后从Str2中截取相应长度的子串为Pattern， *分别的倍数后能否重复出Str1和Str2。

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if len(str2) > len(str1): str1,str2 = str2,str1
        commlen = len(str2)
        for i in range(commlen, 0, -1):
            if len(str1) % i or len(str2) % i:
                continue
            fac1 = len(str1)//i
            fac2 = len(str2)//i
            if str2[:i]*fac1 == str1 and str2[:i]*fac2 == str2:
                return str2[:i]
        return ""

还是把KMP当作模版记下来吧，打车软件公司的面试就被问到了。。。。

def kmp(self, S, P):
        m = len(P)
        n = len(S)
        S = ' ' + S
        P = ' ' + P
        ne = [0]*100010
        res = []
        j = 0
        for i in range(2, m+1):
            while j and P[i] != P[j+1]:
                j = ne[j]
            if P[i] == P[j+1]:
                j += 1
            ne[i] = j
        j = 0
        for i in range(1, n+1):
            while j and S[i] != P[j+1]:
                j = ne[j]
            if S[i] == P[j+1]:
                j += 1
            if j == m:
                res.append(i-j)
                j = ne[j]
        return res