跳到主要内容

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

Author​

zephyr

Description​

Consider an algorithm that calculates a longest palindrome that is a substring of a given string .

Here, we define a string to be a palindrome if for any .

Any string of one character is a palindrome and a string of two characters is a palindrome if and only if .

Answer the following questions.

(1) When is a palindrome, show the condition that is necessary and sufficient for to be a palindrome.

(2) Variable is 1 if is a palindrome, otherwise 0. Show the formula for each of the blanks, , and , in the following iterative equation. is 1 if , otherwise 0.

(3) Show all the initial values of and the procedure of the iterations for calculating by dynamic programming using the above iterative equation.

(4) Explain how to get a longest palindrome that is a substring of using .

考虑一种算法来计算给定字符串 的最长回文子串。

这里，我们定义一个字符串 为回文串，如果对于任意 ，。

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

回答以下问题。

(1) 当 是回文串时，证明 成为回文串的充要条件。

(2) 变量 若 是回文串则为 1，否则为 0。展示以下迭代方程中每个空白的公式，, 和 。 当 时为 1，否则为 0。

(3) 通过使用上述迭代方程，展示所有 的初始值和通过动态规划计算 的迭代过程。

(4) 解释如何使用 获取 的最长回文子串。

Kai​

(1)​

To determine when is a palindrome, we consider the following:

  • Necessary and Sufficient Condition: If is a palindrome, then is also a palindrome if and only if . 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 can be defined as follows:

Here, the blanks can be filled as follows:

Thus, the formula becomes:

Where is a function that returns 1 if and 0 otherwise.

(3)​

Initial Values of ​

  1. For all single character substrings, because every single character is a palindrome.
  2. For two-character substrings, if , otherwise .

Iteration Procedure​

  • For substrings of length 3 and greater, we compute using the formula:
  • Iterate over the lengths of the substrings starting from 3 up to , the length of the string .
  • For each length, iterate over all possible starting indices and calculate the corresponding ending index .
  • Update the value of based on the formula provided.

(4)​

To find the longest palindrome substring using , 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, , and gradually decrease the length. For each length, iterate over all possible starting indices and compute the ending index .
  3. Check Palindrome and Update: For each pair , check if , indicating that the substring is a palindrome. If a palindrome is found, record the starting index 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 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.