東京大学 新領域創成科学研究科 メディカル情報生命専攻 2016年8月実施 問題12

标签：

• Tokyo-University
• Longest-Palindromic-Substring

Author

zephyr

Description

Consider an algorithm that calculates a longest palindrome that is a substring of a given string $x = x_1 \ldots x_m$.

Here, we define a string $y = y_1 \ldots y_n$ to be a palindrome if for any $j$ $(1 \leq j \leq n)$ $y_j = y_{n+1-j}$.

Any string of one character is a palindrome and a string of two characters $y_1 y_2$ is a palindrome if and only if $y_1 = y_2$.

Answer the following questions.

(1) When $x_i \ldots x_j$ is a palindrome, show the condition that is necessary and sufficient for $x_{i-1} \ldots x_{j+1}$ to be a palindrome.

(2) Variable $R(i, j)$ $(1 \leq i \leq m, 1 \leq j \leq m)$ is 1 if $x_i \ldots x_j$ is a palindrome, otherwise 0. Show the formula for each of the blanks, $\text{A}$, $\text{B}$ and $\text{C}$, in the following iterative equation. $\delta(a, b)$ is 1 if $a = b$, otherwise 0.

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

(3) Show all the initial values of $R(i, j)$ and the procedure of the iterations for calculating $R(i, j)$ $(1 \leq i \leq m, 1 \leq j \leq m)$ by dynamic programming using the above iterative equation.

(4) Explain how to get a longest palindrome that is a substring of $x = x_1 \ldots x_m$ using $R(i, j)$ $(1 \leq i \leq m, 1 \leq j \leq m)$.

---

考虑一种算法来计算给定字符串 $x = x_1 \ldots x_m$ 的最长回文子串。

这里，我们定义一个字符串 $y = y_1 \ldots y_n$ 为回文串，如果对于任意 $j$ $(1 \leq j \leq n)$，$y_j = y_{n+1-j}$。

任何一个字符的字符串都是回文串，任何两个字符的字符串 $y_1 y_2$ 是回文串当且仅当 $y_1 = y_2$。

回答以下问题。

(1) 当 $x_i \ldots x_j$ 是回文串时，证明 $x_{i-1} \ldots x_{j+1}$ 成为回文串的充要条件。

(2) 变量 $R(i, j)$ $(1 \leq i \leq m, 1 \leq j \leq m)$ 若 $x_i \ldots x_j$ 是回文串则为 1，否则为 0。展示以下迭代方程中每个空白的公式，$\text{A}$, $\text{B}$ 和 $\text{C}$。 $\delta(a, b)$ 当 $a = b$ 时为 1，否则为 0。

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

(3) 通过使用上述迭代方程，展示所有 $R(i, j)$ 的初始值和通过动态规划计算 $R(i, j)$ $(1 \leq i \leq m, 1 \leq j \leq m)$ 的迭代过程。

(4) 解释如何使用 $R(i, j)$ $(1 \leq i \leq m, 1 \leq j \leq m)$ 获取 $x = x_1 \ldots x_m$ 的最长回文子串。

题目描述

给定字符串 $x=x_1\cdots x_m$，设计动态规划以求其最长回文子串。字符串 $y=y_1\cdots y_n$ 为回文串，当且仅当对每个 $1\le j\le n$ 都有 $y_j=y_{n+1-j}$；任意单字符串都是回文串，双字符 $y_1y_2$ 为回文串当且仅当 $y_1=y_2$。

1. 已知 $x_i\cdots x_j$ 是回文串，给出并证明 $x_{i-1}\cdots x_{j+1}$ 仍为回文串的充要条件。
2. 对 $1\le i,j\le m$，定义
   $$R(i,j)= \begin{cases} 1,&x_i\cdots x_j\text{ 是回文串},\\ 0,&\text{否则}, \end{cases}$$
   且 $\delta(a,b)$ 在 $a=b$ 时为 $1$，否则为 $0$。补全下式中的 A、B、C：
   $$R(i-1,\mathrm A)=\delta(\mathrm B,x_{j+1})R(\mathrm C,j).$$
3. 给出计算全部 $R(i,j)$ 所需的所有初值，并说明使用上述递推式时的迭代顺序。
4. 说明如何从全部 $R(i,j)$ 中取得 $x$ 的一个最长回文子串。

考点

• 最长回文子串：利用子串两端字符相等且内部为回文的充要条件建立状态关系。
• 区间动态规划：正确设置长度为一、长度为二等边界，并按子串长度递增或等价的依赖顺序填表。
• 结果恢复：在所有回文区间状态中比较 $j-i+1$，保存达到最大长度的端点并输出对应连续子串。

Kai

(1)

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

• Necessary and Sufficient Condition: If $x_i \ldots x_j$ is a palindrome, then $x_{i-1} \ldots 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.

(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.

(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.

(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 \ldots 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.

Knowledge

动态规划 回文字符串

解题技巧和信息

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

重点词汇

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

参考资料

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