資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學給定兩個字串，找到它們公共的最長字首迴文子串的長度
在本文中，我們深入探討了字串操作和迴文子串分析領域的一個引人入勝的問題。具體來說，我們將找到兩個給定字串中公共的最長字首迴文子串的長度。我們的解決方案利用了 C、C++、Java 和 Python，這些都是軟體開發人員喜愛的強大而通用的程式語言。
理解迴文子串
迴文子串是指透過重新排列另一個單詞或短語的字母而形成的單詞或短語，通常使用所有原始字母恰好一次。例如，“listen”和“silent”互為迴文子串。
問題陳述
給定兩個字串，我們需要找到這兩個字串中存在的最長字首迴文子串的長度。字首是字串從第一個字元開始的子字串。
解決方案方法
為了解決這個問題，我們將遵循以下步驟：
初始化 - 為每個字串初始化一個大小為 26 的整數陣列（表示 26 個英文字母）。這些陣列將儲存字串字首中每個字元的頻率計數。
頻率計數 - 對於字串字首中的每個字元，增加陣列中對應的索引。
比較 - 比較兩個字串的頻率陣列。找到每個字元的最小頻率，並將這些頻率相加。
返回結果 - 該和是最長公共字首迴文子串的長度。
實現
示例
以下是我們問題解決方案的程式：
#include <stdio.h>
#include <string.h>
int longestCommonPrefixAnagram(char str1[], char str2[]) {
int n1 = strlen(str1), n2 = strlen(str2);
int count1[26] = {0}, count2[26] = {0};
for (int i = 0; i < n1; i++)
count1[str1[i] - 'a']++;
for (int i = 0; i < n2; i++)
count2[str2[i] - 'a']++;
int result = 0;
for (int i = 0; i < 26; i++)
result += (count1[i] < count2[i] ? count1[i] : count2[i]);
return result;
}
int main() {
char str1[] = "abcdef";
char str2[] = "fedcba";
int result = longestCommonPrefixAnagram(str1, str2);
printf("Length of longest common prefix anagram: %d\n", result);
return 0;
}
輸出
Length of longest common prefix anagram: 6
#include <bits/stdc++.h>
using namespace std;
int longestCommonPrefixAnagram(string str1, string str2) {
int n1 = str1.length(), n2 = str2.length();
vector<int> count1(26, 0), count2(26, 0);
for (int i = 0; i < n1; i++)
count1[str1[i] - 'a']++;
for (int i = 0; i < n2; i++)
count2[str2[i] - 'a']++;
int result = 0;
for (int i = 0; i < 26; i++)
result += min(count1[i], count2[i]);
return result;
}
int main() {
string str1 = "abcdef";
string str2 = "fedcba";
int result = longestCommonPrefixAnagram(str1, str2);
cout << "Length of longest common prefix anagram: " << result << endl;
return 0;
}
輸出
Length of longest common prefix anagram: 6
import java.util.Arrays;
public class Main {
public static int longestCommonPrefixAnagram(String str1, String str2) {
int n1 = str1.length();
int n2 = str2.length();
int[] count1 = new int[26];
int[] count2 = new int[26];
for (int i = 0; i < n1; i++) {
count1[str1.charAt(i) - 'a']++;
}
for (int i = 0; i < n2; i++) {
count2[str2.charAt(i) - 'a']++;
}
int result = 0;
for (int i = 0; i < 26; i++) {
result += Math.min(count1[i], count2[i]);
}
return result;
}
public static void main(String[] args) {
String str1 = "abcdef";
String str2 = "fedcba";
int result = longestCommonPrefixAnagram(str1, str2);
System.out.println("Length of longest common prefix anagram: " + result);
}
}
輸出
Length of longest common prefix anagram: 6
def longest_common_prefix_anagram(str1, str2):
n1 = len(str1)
n2 = len(str2)
count1 = [0] * 26
count2 = [0] * 26
for i in range(n1):
count1[ord(str1[i]) - ord('a')] += 1
for i in range(n2):
count2[ord(str2[i]) - ord('a')] += 1
result = 0
for i in range(26):
result += min(count1[i], count2[i])
return result
if __name__ == "__main__":
str1 = "abcdef"
str2 = "fedcba"
result = longest_common_prefix_anagram(str1, str2)
print("Length of longest common prefix anagram:", result)
輸出
Length of longest common prefix anagram: 6
解釋
讓我們考慮以下字串：
str1 = "abcdef", str2 = "fedcba"
在計算每個字元的頻率後，我們發現兩個字串都包含完全相同的字元（儘管順序不同）。因此，最長公共字首迴文子串是整個字串，其長度為 6，這是我們程式的輸出。
結論
查詢兩個字串中公共的最長字首迴文子串長度的問題是一個有趣的問題，它考驗了我們對字串操作和頻率計數的理解。此解決方案說明了如何使用基本的 C、C++、Java 和 Python 程式設計結構來有效地解決它。
更新於: 2023-10-23
267 次瀏覽
廣告