CBMS-2017-12

题目来源：[[文字版题库/CBMS/2017#Problem 12|2017#Problem 12]] 日期：2024-07-29 题目主题：CS-算法-动态规划

解题思路

这个问题涉及在给定字符串中找到最长的回文子串。回文子串的定义是从左到右与从右到左读法相同的子串。我们使用动态规划来解决这个问题，通过构建一个二维数组 $R$ 来存储中间结果。

我们将解答分为以下几个部分：

1. 必要和充分条件：我们首先推导出一个条件，该条件可以确保如果一个子串是回文，那么通过在其两端添加相同字符后，扩展后的字符串仍然是回文。
2. 迭代公式：我们将构建一个表示回文子串的二维数组 $R(i,j)$，其元素为 1 表示子串是回文，0 表示不是。我们需要推导出使用 $R$ 计算下一个状态的迭代公式。
3. 初始值：确定二维数组 $R$ 的初始值。
4. 最终结果：通过遍历 $R$，我们可以找到最长的回文子串。

Solution

Question 1

To determine when $x_{i-1}\dots x_{j+1}$ is a palindrome, we consider the following:

• Necessary and Sufficient Condition: If $x_i\dots x_j$ is a palindrome, then $x_{i-1}\dots x_{j+1}$ is also a palindrome if and only if $x_{i-1}=x_{j+1}$. This means that if we extend a known palindrome by adding the same character at both ends, the resulting string will also be a palindrome.

Question 2

Given the condition above, the iterative formula for $R(i,j)$ can be defined as follows:

$$R(i-1,j+1)=\delta (x_{i-1},x_{j+1})R(i,j)$$

Here, the blanks can be filled as follows:

• $\text{A}=j+1$
• $\text{B}=x_{i-1}$
• $\text{C}=i$

Thus, the formula becomes:

$$R(i-1,j+1)=\delta (x_{i-1},x_{j+1})R(i,j)$$

Where $\delta (a,b)$ is a function that returns 1 if $a=b$ and 0 otherwise.

Question 3

Initial Values of $R(i,j)$

1. For all single character substrings, $R(i,i)=1$ because every single character is a palindrome.
2. For two-character substrings, $R(i,i+1)=1$ if $x_i=x_{i+1}$, otherwise $R(i,i+1)=0$.

Iteration Procedure

• For substrings of length 3 and greater, we compute $R(i,j)$ using the formula:

  $R(i,j)=\delta (x_i,x_j)R(i+1,j-1)$

• Iterate over the lengths of the substrings starting from 3 up to $m$, the length of the string $x$.

• For each length, iterate over all possible starting indices $i$ and calculate the corresponding ending index $j$.

• Update the value of $R(i,j)$ based on the formula provided.

Question 4

To find the longest palindrome substring using $R(i,j)$, follow these steps:

1. Initialize Variables: Set up variables to store the starting index and length of the longest palindrome found so far.
2. Iterate Over Possible Lengths: Start with the maximum possible length of a palindrome, $m$, and gradually decrease the length. For each length, iterate over all possible starting indices $i$ and compute the ending index $j=i+\text{length}-1$.
3. Check Palindrome and Update: For each pair $(i,j)$, check if $R(i,j)=1$, indicating that the substring $x_i\dots x_j$ is a palindrome. If a palindrome is found, record the starting index $i$ and the length of the palindrome. Since the search starts with the longest possible length, this ensures that the first palindrome found will be the longest.
4. Terminate Search Early: Once a palindrome is found, terminate the search, as this will be the longest possible palindrome.
5. Extract the Longest Palindrome: Extract the substring from $x$ starting at the recorded starting index with the recorded length.

This approach optimizes the search by starting with the longest possible length and stopping as soon as a palindrome is found

, ensuring the longest palindrome is identified as quickly as possible.

知识点

动态规划回文字符串

解题技巧和信息

• 对于回文字符串的判断可以使用双指针从两端向中间移动的方法。
• 动态规划表格中，只需关注左上角至右下角的部分，因为回文性质是对称的。

重点词汇

• Palindrome (回文)
• Substring (子串)
• Iterative (迭代)

参考资料

1. “Introduction to Algorithms” by Cormen, Leiserson, Rivest, and Stein, Chap. 25.