資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中指定索引範圍內的迴文子串計數
給定一個字串和一個從start到end的範圍，任務是計算給定範圍內迴文子串的數量。迴文串是指從前向後和從後向前都相同的字串，例如nitin、aba等。
例如
輸入 - InputString = "cccaabbbdee", start = 2, end = 6;
輸出 - 索引範圍內的迴文子串計數：7
說明 - 給定一個範圍和一個字串，我們將從起始指標2（即'c'）遍歷到6（即'b'），因此子串是'caabb'。所以迴文子串是'c'、'a'、'a'、'b'、'b'、'aa'和'bb'。因此，迴文子串的計數是7。
輸入 - InputString = "lioaabbbdee", start = 0, end = 2;
輸出 - 索引範圍內的迴文子串計數：3
說明 - 給定一個範圍和一個字串，我們將從起始指標0（即'l'）遍歷到2（即'o'），因此子串是'lio'。所以迴文子串是'l'、'i'和'o'。因此，迴文子串的計數是3。
下面程式中使用的方法如下
- 宣告一個任意大小的字串和一個從變數start到end的範圍。
- 將資料傳遞給名為palindrome_index(arr, InputString)的函式進行進一步處理
- 在函式內，宣告另一個名為checked的陣列，陣列大小與輸入陣列相同。
- 開始迴圈FOR i 從0到陣列長度
- 在迴圈內，開始另一個迴圈FOR j 從0到陣列長度
- 在迴圈內，設定check為check[i][j] = 0，arr[i][j] = 0
- 開始迴圈FOR i 從長度-1到i大於0
- 在迴圈內，將check和arr的i設定為1，然後開始另一個迴圈FOR j 從i+1到陣列長度
- 在迴圈內，檢查IF字串i等於字串j，並且i+1大於j-1或check[i+1][j-1]不等於0，則將check[i][j]設定為1，否則，將check[i][j]設定為0，然後設定arr[i][j] = arr[i][j-1] + arr[i+1][j] - arr[i+1][j-1] + check[i][j]
- 列印一個二維陣列作為起始和結束。
示例
import java.io.*;
class testqwe {
static void palindrome_index(int arr[][], String s) {
int length = s.length();
int[][] check = new int[length + 1][length + 1];
for (int i = 0; i <= length; i++) {
for (int j = 0; j <= length; j++) {
check[i][j] = 0;
arr[i][j] = 0;
}
}
for (int i = length - 1; i >= 0; i--) {
check[i][i] = arr[i][i] = 1;
for (int j = i + 1; j < length; j++) {
if(s.charAt(i) == s.charAt(j) && (i + 1 > j - 1 || (check[i + 1][j - 1]) != 0)) {
check[i][j] =1;
} else {
check[i][j] =0;
}
arr[i][j] = arr[i][j - 1] + arr[i + 1][j] - arr[i + 1][j - 1] + check[i][j];
}
}
}
public static void main(String args[]) {
String InputString = "cccaabbbdee";
int[][] arr;
arr = new int[50][50];
palindrome_index(arr, InputString);
int start = 2;
int end = 6;
System.out.println("Count of Palindromic substrings in an Index range " + arr[start][end]);
}
}如果我們執行上面的程式碼，它將生成以下輸出：
輸出
Count of Palindromic substrings in an Index range 7
更新於：2021年1月29日
211 次瀏覽
廣告