数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究每个索引的最长回文子串，该子串以该索引开头并以该索引结尾
在本文中，我们将深入探讨字符串算法领域的一个有趣问题：如何在字符串中找到每个索引的最长回文子串，该子串以该索引开头并以该索引结尾。这个问题很有挑战性，特别是对于那些有兴趣掌握各种编程语言中字符串操作技巧的人来说。
回文是指正读和反读都一样的字符串。例如，“madam”就是一个回文。这里的挑战是找到给定字符串中每个索引的最长回文子串，其中子串以该特定索引开头并以该索引结尾。
问题陈述
给定一个字符串，找到每个索引的最长回文子串，使得子串以该索引开头并以该索引结尾。
方法
我们将使用一种称为“Manacher 算法”的方法来解决此问题。该算法通过围绕中心扩展来工作，并且以其在查找最长回文子串方面的效率而闻名。它利用先前计算的信息来避免冗余计算，这使得它比朴素解决方案快得多。
示例
以下是各种编程语言中此操作的实现：
#include <stdio.h>
#include <string.h>
// Function to find the longest palindromic substring centered at each position
void findLongestPalindromicSubstring(char* s, int n, int* result) {
int d1[n];
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 1 : (d1[l + r - i] < r - i + 1) ? d1[l + r - i] : r - i + 1;
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
memcpy(result, d1, sizeof(int) * n);
}
int main() {
char s[] = "bananas";
int n = strlen(s);
int result[n];
findLongestPalindromicSubstring(s, n, result);
for (int i = 0; i < n; i++) {
printf("Index: %d, String: %.*s, Length: %d\n", i, 2 * result[i] - 1, s + i - result[i] + 1, 2 * result[i] - 1);
}
return 0;
}
输出
Index: 0, String: b, Length: 1 Index: 1, String: a, Length: 1 Index: 2, String: ana, Length: 3 Index: 3, String: anana, Length: 5 Index: 4, String: ana, Length: 3 Index: 5, String: a, Length: 1 Index: 6, String: s, Length: 1
#include<bits/stdc++.h>
using namespace std;
vector<int> findLongestPalindromicSubstring(string s) {
int n = s.size();
vector<int> d1(n);
for (int i = 0, l = 0, r = -1; i < n; i++) {
int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
return d1;
}
int main() {
string s = "bananas";
vector<int> result = findLongestPalindromicSubstring(s);
for(int i=0; i<s.size(); i++){
cout << "Index: " << i << ", String: " << s.substr(i-result[i]+1, 2*result[i]-1) << ", Length: " << 2*result[i]-1 << "\n";
}
return 0;
}
输出
Index: 0, String: b, Length: 1 Index: 1, String: a, Length: 1 Index: 2, String: ana, Length: 3 Index: 3, String: anana, Length: 5 Index: 4, String: ana, Length: 3 Index: 5, String: a, Length: 1 Index: 6, String: s, Length: 1
import java.util.Arrays;
public class Main {
public static int[] findLongestPalindromicSubstring(String s) {
int n = s.length();
int[] d1 = new int[n];
int l = 0, r = -1;
for (int i = 0; i < n; i++) {
int k = (i > r) ? 1 : Math.min(d1[l + r - i], r - i + 1);
while (i - k >= 0 && i + k < n && s.charAt(i - k) == s.charAt(i + k)) {
k++;
}
d1[i] = k--;
if (i + k > r) {
l = i - k;
r = i + k;
}
}
return d1;
}
public static void main(String[] args) {
String s = "bananas";
int[] result = findLongestPalindromicSubstring(s);
for (int i = 0; i < s.length(); i++) {
String substring = s.substring(i - result[i] + 1, i + result[i]);
System.out.println("Index: " + i + ", String: " + substring + ", Length: " + (2 * result[i] - 1));
}
}
}
输出
Index: 0, String: b, Length: 1 Index: 1, String: a, Length: 1 Index: 2, String: ana, Length: 3 Index: 3, String: anana, Length: 5 Index: 4, String: ana, Length: 3 Index: 5, String: a, Length: 1 Index: 6, String: s, Length: 1
# Function to find the longest palindromic substring centered at each position
def find_longest_palindromic_substring(s):
n = len(s)
d1 = [0] * n
l, r = 0, -1 # Initialize l and r to 0 and -1, respectively
for i in range(n):
k = 1 if i > r else min(d1[l + r - i], r - i + 1)
while 0 <= i - k and i + k < n and s[i - k] == s[i + k]:
k += 1
d1[i] = k - 1
if i + k - 1 > r:
l = i - k + 1
r = i + k - 1
return d1
if __name__ == "__main__":
s = "bananas"
result = find_longest_palindromic_substring(s)
for i in range(len(s)):
print(f"Index: {i}, String: {s[i-result[i]+1:i+result[i]+1]}, Length: {2*result[i]+1}")
输出
Index: 0, String: b, Length: 1 Index: 1, String: a, Length: 1 Index: 2, String: ana, Length: 3 Index: 3, String: anana, Length: 5 Index: 4, String: ana, Length: 3 Index: 5, String: a, Length: 1 Index: 6, String: s, Length: 1
函数 findLongestPalindromicSubstring 以字符串 s 作为输入，并返回一个整数向量，其中向量的每个索引 i 存储字符串中以索引 i 开头并以索引 i 结尾的最长回文子串的最大长度。
在此测试用例中，输入字符串为“bananas”。findLongestPalindromicSubstring 函数以该字符串作为参数被调用，结果存储在 result 向量中。然后，对于每个索引，相应的最大长度回文子串及其长度将被打印出来。
结论
查找字符串中每个索引的最长回文子串可能是一个具有挑战性的问题，但是有了合适的算法，例如 Manacher 算法，就可以有效地解决它。我们希望本文能让你清楚地了解如何处理和解决此问题。
更新于：2023年10月23日
135 次浏览
广告