Google Kick Start 2022 年 E 轮回文匹配问题

Question

Google Kick Start E 轮刚刚结束，我无法弄清楚我在实施回文匹配问题时错过了哪些边缘情况。

问题： 给你一个长度为 N 的回文字符串 P，仅由英文字母表中的小写字母组成。找到最短的非空回文串 Q，使得 P 与 Q 连接形成回文。形式上，字符串 PQ 形成一个回文。

输入： 输入的第一行给出测试用例的数量，T。T测试用例跟随。每个测试用例由两行组成。每个测试用例的第一行包含一个整数N，表示字符串P的长度。每个测试用例的第二行包含一个长度为N的回文字符串P。

输出：对于每个测试用例，输出一行包含 Case #x: y，其中 x 是测试用例编号（从 1 开始），y 是非空回文串 Q，如上所述。

这是完整问题的链接：

https://codingcompetitions.withgoogle.com/kickstart/round/00000000008cb0f5/0000000000ba82c5

我的总体想法是迭代给定的回文并确定是否可以将当前索引处的字符串拆分为两个回文。我可以的第一个​​实例是最短的非空回文字符串，我可以将其连接到给定回文的末尾以形成一个新的回文。这是我写的第二次检查时卡住的内容：

import fileinput

cases = 0
total_cases = 0
length = 0

def check_palindrome(st,en, s):
    while(st < en):
        if s[st] == s[en]:
            st += 1
            en -=1
        else:
            return False
    return True

def solve(s):
    for i in range(1,len(s) - 1):
        if check_palindrome(i, len(s) - 1, s) and check_palindrome(0, i - 1, s):
            return s[0:i]
    return s

for line in fileinput.input():
    if fileinput.isfirstline():
        total_cases = int(line.strip())
        continue
    elif cases == total_cases:
        break
    else:
        if fileinput.lineno() % 2 == 0:
            length = int(line.strip())
        else:
            s = solve(line.strip())
            cases += 1
            print(f'Case #{cases}: ' + s)

以下是我最初的尝试，但出现了时间限制错误。出于某种原因，我的第一次尝试似乎澄清了我的第二次尝试失败的情况。老实说，我似乎找不到我所做的不同之处：

def check_palindrome(st,en, s):
    while(st < en):
        if s[st] == s[en]:
            st += 1
            en -=1
        else:
            return False
    return True

def solve(s):
    st= 1
    sol = s[0]
    while(st < len(s)):
        if check_palindrome(st, len(s) - 1, s) and check_palindrome(0, len(sol) - 1, sol):
            return sol
        else:
            sol = s[st] + sol
            st += 1
    return sol

我还感觉我的方法还可以进一步优化。如果有人能指出我正确的方向，我将不胜感激。

Answer 1

鉴于 P 和 Q 都是回文，并且 PQ 必须是回文，有以下观察结果：

• 因为PQ是回文，所以Q是P的前缀

• 所以 P 要么是 Q 本身，要么 P 是 QR，其中 R 必须是回文

  • 由于QR是回文，所以Q必须是R的后缀
  • 所以 R 要么是 Q 本身，要么 R 是...等

结论：P一定是Q的重复。

这意味着您可以应用这种方法：

• 识别 len(P) 的所有整数除数，包括 len(P) 本身：这些是 len(Q) 的唯一候选者
• 按升序迭代 P 的整数除数列表，直到 P 的相应前缀使得 P 是它的重复。
• 该前缀是 Q。

注意：不需要对 Q 进行回文测试，因为它是根据我们确认 Q 既是 P 的前缀又是后缀的事实得出的，所以因为 P 被指定为回文，所以 Q 是它自己的反转，即回文。

执行

from sympy import divisors  # or use any other efficient implementation

def solve(P):
    lenP = len(P)
    for n in divisors(lenP):
        Q = P[:n]
        if P == Q * (lenP // n):
            return Q