无法理解寻找最长回文子串的解决方案之一
One of the solution for finding the longest palindromic substring could not be understood
参考这个article on leetcode，求解最长回文子串问题有一个常见的错误：
Reverse S and become S’. Find the longest common substring between S and S’, which must also be the longest palindromic substring.
例如：
S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.
但是下面的整改我看不太懂。谁能一步一步解释一下procedure/example？谢谢！
To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices.
有一些有效的算法可以通过反转原始子串来计算最长回文子串。例如，以下内容：
1) 创建一个广义字符串 S1#S2$，它需要 O(n)
1) 构造一个后缀数组 O(n) -> 不简单，但是有简单的 O(nlogn) 和 O(nlog^2n) 算法
2) 构造一个 lcp 数组 O(n) -> trivial（还有一个 trivial O(nlogn) 的）。
3) 构造一个 RMQ 数据结构：O(n) 构造和 O(1) 查询 -> 不平凡（有平凡的 O(nlogn) 构造和 O(logn) 查询）
4) 遍历原始字符串 S1 中的每个位置 i。在广义字符串中找到 S2 中的补码位置。找到最长的公共前缀：O(1)
一般来说，对于偶数和奇数长度的回文，必须修改上述方法。不同之处在于，在奇数长度回文中，您只是在选择索引时引入了一个间隙。
这产生了该问题的 O(n) 解。
关于文章：
作者提到找到最长公共子串是不够的，因为具有这种lcp的两个子串在原始字符串中可能不是邻居。
因此，我们要找到两个字符串 A 和 B，一个属于 S1，一个属于 S2，这样 lcp(A,B) 最大，但也是 A 。 rev(B) 在原来的 S1 中。
希望我说得够清楚了。
我被困在那里，所以我 google 到达这里。下面我understand.Let我以作者提到的原始String为例
S = "caba', S' = "abac", so longest common substring is aba.
句子是"we check if the substring’s indices are the same as the reversed substring’s original indices."
1.What 是子串的索引？
"aba" is [1, 2, 3]
2.what 是反转子串的原始索引吗？
反转后的子串是"aba"，其原始索引也是[1, 2, 3].
所以这个答案是正确的。
我们正在看另一个例子。
S="abacdfgdcaba", S' = "abacdgfdcaba", so longest common substring is "abacd".
同样的过程：
1.What 是子串的索引？
"abacd" is [0, 1, 2, 3, 4].
2.what 是反转子串的原始索引吗？
反转后的子串是 "abacd"，但其原始索引也是 [7, 8, 9, 10, 11]。
所以这两个"abacd"不是同一个，答案不正确。
我觉得那句话有点绕口，我觉得作者写的有点难懂。
我觉得这句话应该改成"To rectify this, each time we find a longest common substring candidate, we check if the substring are the same one as the reversed substring’."
如果有人正在寻找这个问题的实现，我们使用最长公共子串来查找最长回文子串，这是我的版本。
package leetcodeproblems;
/**
* Created by Nandan Mankad on 23-11-19.
*/
public class LongestPalindromicSubstring {
public static void main(String[] args) {
/*String s = "aacdefcaa";*/
/*String s = "dabcbae";*/
/*String s = "babad";*/
/*String s = "cbbd";*/
/*String s = "cbbc";*/
String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
System.out.println(longestPalindrome(s));
}
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return s;
}
StringBuilder sb = new StringBuilder(s);
String revString = sb.reverse().toString(); // Reversing the string - to compute LCS.
int dp[][] = new int[s.length() + 1][s.length() + 1];
int maxLength = 0;
int iPos = 0;
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp.length; j++) {
if (s.charAt(i - 1) == revString.charAt(j - 1)) { // Character matches in Original String and Reversed String.
dp[i][j] = dp[i - 1][j - 1] + 1; // Standard Longest Common Substring logic for Original and Reversed String.
int revIdx = i;
int forIdx = j - dp[i][j] + 1;
if (s.length() - revIdx + 1 == forIdx) { // Here we check if the reverse string original idx is same as original string idx.
if (maxLength < dp[i][j]) {
maxLength = dp[i][j];
iPos = i;
}
}
} else {
dp[i][j] = 0;
}
}
}
StringBuilder res = new StringBuilder();
while (maxLength > 0) {
res.append(s.charAt(iPos- 1));
maxLength--;
iPos--;
}
return res.toString();
}
}
该题通过了Leetcode上的所有测试用例。即兴创作可能是我们反向迭代字符串而不是反转实际字符串等的地方
时间复杂度：O(N^2)
Space 复杂度：O(N^2)
我刚开始接触 leetcode，偶然发现了上述文章。
试图实现完全相同的逻辑。成功了，但效率不如上面提到的 DP 方案Longest palindromic substring | Dynamic programming
您可以简单地检查范围是否相等来实现算法中的逻辑。
这是我实现这篇文章的解决方案。需要一个运行时间
364 毫秒，仅比 21.99% 的 C++ 在线提交快
class Solution {
public:
string longestPalindrome(string s) {
int max = 0,temp,mr=0;
string revs = s;
reverse(revs.begin(), revs.end());
string soln;
int l = s.size();
if(l==0 || l==1) return s;
int dp[l+1][l+1];
for(int row = 0; row < l; row ++)
for(int col = 0; col < l; col ++){
if(s.at(row) != revs.at(col))
dp[row+1][col+1] = 0;
else{
if(row==0 or col ==0) temp = 1;
else temp = dp[row][col] + 1;
dp[row+1][col+1] = temp;
if(temp > max && row-temp+1 == l-col -1 && l-row -1 == col-temp +1 ){
mr = row;max = temp;
}
}
}
/* for(int row = 0; row < l+1; row ++){
for(int col = 0; col < l+1; col ++){
if(row == 0 && col > 0)
cout << revs.at(col-1) << ", ";
else if(col == 0 && row > 0)
cout << s.at(row-1) << ", ";
else
cout << dp[row][col] << ", ";
}
cout << endl;
}
cout << "\n___________\nmax:" << max <<"\nmr: " << mr << "\n"; */
//return (max>1)?s.substr(mr-max+1,max):s.substr(0,1);
return s.substr(mr-max+1,max);
}
};
参考这个article on leetcode，求解最长回文子串问题有一个常见的错误：
Reverse S and become S’. Find the longest common substring between S and S’, which must also be the longest palindromic substring.
例如：
S = “abacdfgdcaba”, S’ = “abacdgfdcaba”.
The longest common substring between S and S’ is “abacd”. Clearly, this is not a valid palindrome.
但是下面的整改我看不太懂。谁能一步一步解释一下procedure/example？谢谢！
To rectify this, each time we find a longest common substring candidate, we check if the substring’s indices are the same as the reversed substring’s original indices.
有一些有效的算法可以通过反转原始子串来计算最长回文子串。例如，以下内容：
1) 创建一个广义字符串 S1#S2$，它需要 O(n)
1) 构造一个后缀数组 O(n) -> 不简单，但是有简单的 O(nlogn) 和 O(nlog^2n) 算法
2) 构造一个 lcp 数组 O(n) -> trivial（还有一个 trivial O(nlogn) 的）。
3) 构造一个 RMQ 数据结构：O(n) 构造和 O(1) 查询 -> 不平凡（有平凡的 O(nlogn) 构造和 O(logn) 查询）
4) 遍历原始字符串 S1 中的每个位置 i。在广义字符串中找到 S2 中的补码位置。找到最长的公共前缀：O(1)
一般来说，对于偶数和奇数长度的回文，必须修改上述方法。不同之处在于，在奇数长度回文中，您只是在选择索引时引入了一个间隙。
这产生了该问题的 O(n) 解。
关于文章：
作者提到找到最长公共子串是不够的，因为具有这种lcp的两个子串在原始字符串中可能不是邻居。
因此，我们要找到两个字符串 A 和 B，一个属于 S1，一个属于 S2，这样 lcp(A,B) 最大，但也是 A 。 rev(B) 在原来的 S1 中。
希望我说得够清楚了。
我被困在那里，所以我 google 到达这里。下面我understand.Let我以作者提到的原始String为例
S = "caba', S' = "abac", so longest common substring is aba.
句子是"we check if the substring’s indices are the same as the reversed substring’s original indices."
1.What 是子串的索引？
"aba" is [1, 2, 3]
2.what 是反转子串的原始索引吗？ 反转后的子串是"aba"，其原始索引也是[1, 2, 3].
所以这个答案是正确的。
我们正在看另一个例子。
S="abacdfgdcaba", S' = "abacdgfdcaba", so longest common substring is "abacd".
同样的过程：
1.What 是子串的索引？
"abacd" is [0, 1, 2, 3, 4].
2.what 是反转子串的原始索引吗？
反转后的子串是 "abacd"，但其原始索引也是 [7, 8, 9, 10, 11]。
所以这两个"abacd"不是同一个，答案不正确。
我觉得那句话有点绕口，我觉得作者写的有点难懂。
我觉得这句话应该改成"To rectify this, each time we find a longest common substring candidate, we check if the substring are the same one as the reversed substring’."
如果有人正在寻找这个问题的实现，我们使用最长公共子串来查找最长回文子串，这是我的版本。
package leetcodeproblems;
/**
* Created by Nandan Mankad on 23-11-19.
*/
public class LongestPalindromicSubstring {
public static void main(String[] args) {
/*String s = "aacdefcaa";*/
/*String s = "dabcbae";*/
/*String s = "babad";*/
/*String s = "cbbd";*/
/*String s = "cbbc";*/
String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
System.out.println(longestPalindrome(s));
}
public static String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return s;
}
StringBuilder sb = new StringBuilder(s);
String revString = sb.reverse().toString(); // Reversing the string - to compute LCS.
int dp[][] = new int[s.length() + 1][s.length() + 1];
int maxLength = 0;
int iPos = 0;
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp.length; j++) {
if (s.charAt(i - 1) == revString.charAt(j - 1)) { // Character matches in Original String and Reversed String.
dp[i][j] = dp[i - 1][j - 1] + 1; // Standard Longest Common Substring logic for Original and Reversed String.
int revIdx = i;
int forIdx = j - dp[i][j] + 1;
if (s.length() - revIdx + 1 == forIdx) { // Here we check if the reverse string original idx is same as original string idx.
if (maxLength < dp[i][j]) {
maxLength = dp[i][j];
iPos = i;
}
}
} else {
dp[i][j] = 0;
}
}
}
StringBuilder res = new StringBuilder();
while (maxLength > 0) {
res.append(s.charAt(iPos- 1));
maxLength--;
iPos--;
}
return res.toString();
}
}
该题通过了Leetcode上的所有测试用例。即兴创作可能是我们反向迭代字符串而不是反转实际字符串等的地方
时间复杂度：O(N^2) Space 复杂度：O(N^2)
我刚开始接触 leetcode，偶然发现了上述文章。
试图实现完全相同的逻辑。成功了，但效率不如上面提到的 DP 方案Longest palindromic substring | Dynamic programming
您可以简单地检查范围是否相等来实现算法中的逻辑。
这是我实现这篇文章的解决方案。需要一个运行时间 364 毫秒，仅比 21.99% 的 C++ 在线提交快
class Solution {
public:
string longestPalindrome(string s) {
int max = 0,temp,mr=0;
string revs = s;
reverse(revs.begin(), revs.end());
string soln;
int l = s.size();
if(l==0 || l==1) return s;
int dp[l+1][l+1];
for(int row = 0; row < l; row ++)
for(int col = 0; col < l; col ++){
if(s.at(row) != revs.at(col))
dp[row+1][col+1] = 0;
else{
if(row==0 or col ==0) temp = 1;
else temp = dp[row][col] + 1;
dp[row+1][col+1] = temp;
if(temp > max && row-temp+1 == l-col -1 && l-row -1 == col-temp +1 ){
mr = row;max = temp;
}
}
}
/* for(int row = 0; row < l+1; row ++){
for(int col = 0; col < l+1; col ++){
if(row == 0 && col > 0)
cout << revs.at(col-1) << ", ";
else if(col == 0 && row > 0)
cout << s.at(row-1) << ", ";
else
cout << dp[row][col] << ", ";
}
cout << endl;
}
cout << "\n___________\nmax:" << max <<"\nmr: " << mr << "\n"; */
//return (max>1)?s.substr(mr-max+1,max):s.substr(0,1);
return s.substr(mr-max+1,max);
}
};