从两个字符串构建回文

Question

我想写一个Python函数来有效地做到这一点：

该函数将采用两个字符串“a”和“b”，并尝试找到最长的回文字符串 可以这样形成，即它是“a”的非空子字符串和非空子字符串的串联 'b' 的子串。如果有多个有效答案，它将返回字典顺序最小的一个。 如果无法形成这样的字符串，则返回'-1'。

我有一个低效的解决方案，它生成两个字符串的所有子字符串，然后创建所有可能的串联，同时跟踪最长的有效回文：

def is_palindrome(word):
    """Check if a word is a palindrome."""
    reversed_word = word[::-1]
    return word == reversed_word


def all_substrings_of_word(word):
    """Generate all possible non-empty substrings of a given string."""
    substrings = []
    for sub_string_length in range(1, len(word) + 1):
        for i in range(len(word) - sub_string_length + 1):
            new_word = word[i:i + sub_string_length]
            substrings.append(new_word)
    return substrings


def buildPalindrome(a, b):
    """Attempt to find the longest palindromic string created by concatenating
    a substring of `a` with a substring of `b`."""
    sub_strings_a = all_substrings_of_word(a)
    sub_strings_b = all_substrings_of_word(b)

    # Generate all possible concatenations of substrings from `a` and `b`
    multiplexed_array = [
        word_a + word_b for word_a in sub_strings_a for word_b in sub_strings_b]

    # Find the best palindrome (longest, then lexicographically smallest)
    best_palindrome = ""
    for word in multiplexed_array:
        if is_palindrome(word):
            if len(word) > len(best_palindrome):
                best_palindrome = word
            elif len(word) == len(best_palindrome) and word < best_palindrome:
                best_palindrome = word

    return best_palindrome if best_palindrome else "-1"

print(buildPalindrome("bac", "bac"))   # EXPECTED OUTPUT -- aba
print(buildPalindrome("abc", "def"))   # EXPECTED OUTPUT -- -1
print(buildPalindrome("jdfh", "fds"))   # EXPECTED OUTPUT -- dfhfd

我可以得到如何改进的解释吗？

Answer 1

您的问题本质上可以归结为“最长公共子串”问题。 B，反转它，然后使用

广义后缀树

在

A

时间内找到

B

和O(|A| + |B|)之间的最长公共子串（使用

Ukkonen算法构建具有相同复杂性的树） 

）。 一旦有了这个子字符串

S

，您需要确定该子字符串是否仅作为

A

的后缀和

B

的（反转）前缀存在，或者是否也出现在其他任何地方。您可以通过遵循树中的路径

S

来查询后缀树，并检查它是否有任何子级。如果它确实有孩子（

S

不仅仅是前缀/后缀对），那么最长的回文将是

...XYX...

的形式，所以我们将

X

的长度加倍并添加

1

。否则它将是

...XX...

，我们只需将长度加倍即可。这将为您提供总体上

O(|A| + |B|)

时间的结果，以及相同的空间复杂性。如果您需要回文本身，只需将

S

的反向连接到自身，如有必要，在它们之间插入来自后缀树中

S

子代的附加字符。