在python中查找字符串连接的最小除数

Question

我有一个接受两个字符串的函数，我试图检查一个字符串是否可以被另一个字符串整除，一个字符串可以被扩展任意次数以匹配另一个字符串的长度，如果出现这种情况，我需要返回一个字符串可以被另一个字符串整除所需的最小连接数：

这是我的尝试：

def findSmallestDivisor(s, t):
    s_count = len(s)
    t_count = len(t)
    if s_count % t_count ==0:
        return t_count

假设s=bcdbcdbcdbcd和t=bcdbcd，那么它需要从t得到唯一字符串bcd的两个浓缩，以被s整除

我想返回唯一集的长度，以防它是可除的，在上面的例子中是3

根据要求添加更多示例：

假设字符串s=lrbblrbb和字符串t=lrbb，那么如果我将字符串t加倍，它将被字符串s整除，因为字符串t有长度4，这应该是答案，但是在我上面提到的示例中，棘手的部分是当s=bcdbcdbcdbcd和t=bcdbcd。答案应该是3，而不是6，因为bcd是唯一集，而t中的另一个bcd只是重复

Answer 1

通过简单的模式检测和字符串扩展，试试这个

代码

def extend(s, t):
    """
    Extend t and check with s.
    """
    ret = None
    newt = t

    while True:
        newt = newt + t
        if len(s) % len(newt) == 0:
            ret = newt
            break

        if len(newt) > len(s):
            ret = None
            break

    return ret


def pattern(t):
    """
    Pattern detection by 2, (limited edition).
    Split t into 2 and compare, if the same then they are just doubled.
    If not then it is already unique.
    """
    ret = None
    t_count = len(t)

    if t_count >= 2:
        t1 = t[0:t_count//2]
        t2 = t[t_count//2:]

        # If the same then 1 part is the pattern.        
        if t1 == t2:
            ret = len(t1)
        # If not then the whole t itself is the pattern.
        else:
            ret = len(t)
    # Else if string length is less than 2 then just return 1 assuming t is not empty
    else:
        ret = 1  # unique

    return ret


def findSmallestDivisor(s, t):
    ret = None
    s_count = len(s)
    t_count = len(t)

    # Check if existing length of s is already divisible by existing length t
    if s_count % t_count == 0:
        ret = pattern(t)

    # Else if not divisible then we will extend t.
    else:
        newt = extend(s, t)
        if newt is not None:
            ret = pattern(t)

    return ret


def findSmallestDivisor(s, t):
    ret = None
    s_count = len(s)
    t_count = len(t)

    # Check if existing length of s is already divisible by existing length t.
    if s_count % t_count == 0:
        ret = pattern(t)

    # Else if not divisible then we will extend t.
    else:
        newt = extend(s, t)
        if newt is not None:
            ret = pattern(t)

    return ret


tests = {
    1: {
        's': 'bcdbcdbcdbcd',
        't': 'bcdbcd'
    },
    2: {
        's': 'lrbblrbb',
        't': 'lrbb'
    },
    3: {
        's': 'lrbblrbb',
        't': 'lrb'
    }
}


# Tests
data = []
for k, v in tests.items():
    s = v['s']
    t = v['t']
    data.append({'testnum': k, 's': s, 't': t, 'res': findSmallestDivisor(s, t)})

df = pd.DataFrame(data)
print(df.to_string())

输出

   testnum             s       t  res
0        1  bcdbcdbcdbcd  bcdbcd  3.0
1        2      lrbblrbb    lrbb  4.0
2        3      lrbblrbb     lrb  NaN