東京大学 新領域創成科学研究科 メディカル情報生命専攻 2016年8月実施 問題12
Author
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.
(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。
(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\) 的最长回文子串。
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:
Here, the blanks can be filled as follows:
- \(\text{A} = j + 1\)
- \(\text{B} = x_{i-1}\)
- \(\text{C} = i\)
Thus, the formula becomes:
Where \(\delta(a, b)\) is a function that returns 1 if \(a = b\) and 0 otherwise.
(3)
Initial Values of \(R(i, j)\)
- For all single character substrings, \(R(i, i) = 1\) because every single character is a palindrome.
- 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:
- 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:
- Initialize Variables: Set up variables to store the starting index and length of the longest palindrome found so far.
- 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\).
- 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.
- Terminate Search Early: Once a palindrome is found, terminate the search, as this will be the longest possible palindrome.
- 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 (迭代)
参考资料
- "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, Chap. 25.