資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中字串特殊迴文子串的計數
給定一個字串 str。目標是計算 str 的所有子字串，這些子字串是特殊的迴文，並且長度大於 1。特殊的迴文是指所有字元都相同或只有中間字元不同的字串。例如，如果字串是“baabaa”，則原始字串的特殊迴文子字串是“aa”、“aabaa”、“aba”、“aa”。
讓我們透過例子來理解。
輸入 − str=”abccdcdf”
輸出 − 字串中特殊迴文子串的計數為 − 3
說明 − 特殊迴文子串為 − “cc”, “cdc”, “dcd”
輸入 − str=”baabaab”
輸出 − 字串中特殊迴文子串的計數為 − 4
說明 − 特殊迴文子串為 − “aa”, “aabaa”, “aba”, “aa”
下面程式中使用的方法如下
建立一個字母字串並計算其長度。將資料傳遞給函式以進行進一步處理。
宣告臨時變數 count 和 i 並將其設定為 0
建立一個大小為字串的陣列並將其初始化為 0。
開始 WHILE 直到 i 小於字串的長度
在 while 內部，將一個變數設定為 total 為 1，並將變數 j 設定為 i + 1
開始另一個 WHILE 直到 str[i] = str[j] 並且 j 小於字串的長度
在 while 內部，將 total 加 1 並將 j 加 1
將 count 設定為 count + ( total * (total + 1) / 2, arr[i] 設定為 total 並將 i 設定為 j
從 j 到 1 開始迴圈 FOR 直到字串的長度
檢查 str[j] 是否等於 str[j-1]，然後將 arr[j] 設定為 arr[j-1]
將變數 temp 設定為 str[j-1] 並檢查 j > 0 並且 j < 字串長度減 1 並且 temp = str[j+1] 並且 sr[j]!=temp，然後將 count 設定為 count + min(arr[j-1], arr[j+1])
將 count 設定為 count - 字串的長度
返回 count
列印結果。
示例
#include <bits/stdc++.h>
using namespace std;
int count_palindromes(string str, int len){
int count = 0, i = 0;
int arr[len] = { 0 };
while (i < len){
int total = 1;
int j = i + 1;
while (str[i] == str[j] && j < len){
total++;
j++;
}
count += (total * (total + 1) / 2);
arr[i] = total;
i = j;
}
for (int j = 1; j < len; j++){
if (str[j] == str[j - 1]){
arr[j] = arr[j - 1];
}
int temp = str[j - 1];
if (j > 0 && j < (len - 1) && (temp == str[j + 1] && str[j] != temp)){
count += min(arr[j-1], arr[j+1]);
}
}
count = count - len;
return count;
}
int main(){
string str = "bcbaba";
int len = str.length();
cout<<"Count of special palindromes in a String are: "<< count_palindromes(str, len);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of special palindromes in a String are: 3
580 次瀏覽
