資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 統計給定字串中不重疊迴文子字串的對數
給定一個字串作為輸入，任務是找出給定輸入字串中不重疊迴文子字串的對數。如果子字串是迴文，則 arr[i][j] 的值為真，否則為假。我們將從字串中取出組合，並檢查這些對是否滿足條件。
讓我們透過示例來理解。
輸入：ABC
輸出：不重疊迴文子字串的對數為 3
解釋：可能的對是 (A) (B) (C) ，(A) (BC)，(AB) (C)，(ABC)
輸入：ABCD
輸出：不重疊迴文子字串的對數為 8
解釋：可能的對是 (A)(B)(C)(D)，(A)(B)(CD)，(A)(BC)(D)，(A)(BCD)，(AB)(C)(D)，(AB)(CD)，
(ABC)(D)，(ABCD)
下面程式中使用的方案如下
- 將字串作為輸入，並將其傳遞給函式 pair_count(text) 進行進一步處理。
- 最初建立了一個大小為 100 的布林型二維陣列 arr[ ][ ]，並保持自底向上填充，並將輸入字串 (text) 轉換為字元陣列。
- 然後透過檢查值 arr[i+1][j-1] 來計算陣列，如果該值為真且 str[i] 與 str[j] 相同，則我們將 arr[i][j] 設定為真。否則，arr[i][j] 的值設定為假。
- 之後初始化 start[ ] 和 end[ ]，start[i] 儲存索引左側迴文數（包括 i），end[i] 儲存索引右側迴文數（包括 i）。
- 然後迭代一個從 0 到 str.length() - 1 的迴圈，並在迴圈內部透過將結果與 start[i] * end[i + 1] 的乘積相加來計算結果。
示例
import java.io.*;
import java.util.*;
class tutorialPoint {
static int SIZE = 100;
static int pair_count(String str) {
boolean arr[][] = new boolean[SIZE][SIZE];
char[] ch = str.toCharArray();
for (int i = 0; i < ch.length; i++) {
for (int j = 0; j < ch.length; j++) {
arr[i][j] = false;
}
}
for (int j = 1; j <= ch.length; j++) {
for (int i = 0; i <= ch.length - j; i++) {
if (j <= 2) {
if (ch[i] == ch[i + j - 1]) {
arr[i][i + j - 1] = true;
}
} else if (ch[i] == ch[i + j - 1]) {
arr[i][i + j - 1] = arr[i + 1][i + j - 2];
}
}
}
int start[] = new int[str.length()];
int end[] = new int[str.length()];
start[0] = 1;
for (int i = 1; i < str.length(); i++) {
for (int j = 0; j <= i; j++) {
if (arr[j][i] == true) {
start[i]++;
}
}
}
end[str.length() - 1] = 1;
for (int i = str.length() - 2; i >= 0; i--) {
end[i] = end[i + 1];
for (int j = str.length() - 1; j >= i; j--) {
if (arr[i][j] == true) {
end[i]++;
}
}
}
int result = 0;
for (int i = 0; i < str.length() - 1; i++) {
result = result + start[i] * end[i + 1];
}
return result;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in); //ABCD
String text = scan.next();
System.out.println("Count pairs of non-overlapping palindromic sub-strings is\t" + pair_count(text));
}
}如果我們執行以上程式碼，它將生成以下輸出：
輸出
Count pairs of non-overlapping palindromic sub-strings is 8
更新於： 2021-01-29
331 次檢視
廣告