排列并以更少的递归查找相同的字符串

Question

我目前在解决课程中的编程问题时遇到了一些困难。

问题如下：

给定 k 个不同的小写英文字符串，如果第 i 个和第 j 个字符串的串联产生一个新字符串 X，可以拆分为两个相同的子字符串 {x,x}，请返回 i 和 j 的所有可能组合。

约束条件是 k<80000 and the length of each string is <200.

我编写了一个可以正常运行的程序，但它的时间复杂度是 O(k*(k-1)/2)。我现在正在尝试将其时间复杂度降低到 O(k*string_length)，但我不确定如何实现。

这是我当前的代码：

def pair2(strSet, k):
    ans = 0
    ans_set = set()
    runtime = 0
    for i in range(k):
        ele1 = strSet[i]
        for j in range(i + 1, k):
            ele2 = strSet[j]
            runtime += 1
            new_ele = ele1 + ele2
            if len(new_ele) % 2 == 0:
                half = len(new_ele) // 2
                left_ele = new_ele[:half]
                right_ele = new_ele[half:]
                if left_ele == right_ele and (ele1, ele2) not in ans_set and (ele2, ele1) not in ans_set:
                    ans += 1
                    ans_set.add((ele1, ele2))
    #print(runtime)
    return ans

k = 5 
strSet = ['aca', 'baab', 'c', 'aa', 'bacab']
print(pair2(strSet, k))
#output is 3

k = 7 
strSet = ['aaaa', 'a', 'aaa', 'c', 'bbcbb', 'kkk', 'abcdcd']
print(pair2(strSet, k))
#output is 2