主页 / 问题 / 1392892
Accepted
trapper
Asked:2022-08-23 20:37:09 +0800 CST2022-08-23 20:37:09 +0800 CST

如何优化python中的算法？

  • 772

在此处输入图像描述

def checking_for_substring(string_line, test_substring):
    substring=''.join(test_substring)
    if len(string_line)%len(substring)!=0:
        return False
    elif len(string_line)==len(substring):
        return True
    flag=0
    for index_string_line in range(0,len(string_line),len(substring)):  #index_limit() -> len(string_line)
        for index_substring in range(len(substring)):
            if string_line[index_string_line]==substring[index_substring]:
                index_string_line+=1
                flag+=1
        if flag==len(substring):
            flag=0
        else:
            return False
    return True

def main():
    string_line=str(input())
    test_substring=list()
    for i in range(len(string_line)):
        test_substring.append(string_line[i])
        if checking_for_substring(string_line, test_substring)==True:
            break
    print(int(len(string_line)/len(test_substring)))

if __name__=="__main__":
    main()

如何优化这个算法，使运行时间小于 1 秒。

TK：给出一个非空字符串S。你需要找到这样一个最大的数字k和一个与连续写出一次T的字符串S匹配的字符串。Tk

示例：
输入：aaaaa
输出：5
输入：abcabcabc
输出：3
输入：abab
输出：2

python

2 个回答

  1. 我会采取不同的行动。我们寻找字符串长度除数并检查它们的字符串。

    就我对 Python 的了解不足而言，结果是这样的（可能你可以写得更好）：

    S = input()
for m in range(len(S),0,-1):
    k = len(S)//m
    if k*m != len(S):
        continue
    t = S[:k]
    p = ""
    for i in range(1,m+1):
        p = p + t
    if p == S:
        print(m)
        break
    • 2
  2. Best Answer

    使用 z 函数在线性时间内求解。
    z[i] 是字符串 s 的最长公共前缀及其第 i 个后缀的长度。
    如果 z[i]=ni 并且 n 可以被 i 整除，则 i 是最短的可重复段长度。
    对于给定的示例z[4] = 8，即 s[4:]==s[:8],8与12 - 4, 段长 4 重合，重复 3 次。

    def z_function(s):
    n = len(s)
    z = [0]*n
    l = 0
    r = 0
    for i in range(1, n):
        if (i <= r):
            z[i] = min (r-i+1, z[i-l])
        while (i+z[i] < n) and (s[z[i]] == s[i+z[i]]):
            z[i] += 1
        if (i+z[i]-1 > r):
            l = i
            r = i+z[i]-1
    return z

s = 'abcdabcdabcd'
z = z_function(s)
n = len(s)
for i,x in enumerate(z):
    if i+x==n and n%i==0:
        print(n//i, s[:i])
        break

>>>   3  abcd
    • 1

相关问题