資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告