資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學統計字串的迴文特性
在C++環境中，迴文是一種特性，在獲得結果後我們得到相同的值。假設有一個表示為S的字串，長度為N。現在我們需要對該字串執行一個操作，以查詢給定範圍內的k-迴文數，即迴文特性。
這是一個過程的一般示例：
Input for the process : abba Output by the process : 6 1 0 0 Explanation of the method: "6" 1-palindromes numbers operation = "a", "b", "b", "a", "bb", "abba". "1" 2-palindromes numbers operation = "bb". Because "b" is 1-palindrome number and "bb" has both left and right parts both are equal. "0" 3-palindrome and 4-palindrome.
統計字串迴文字元的演算法
在這個可能的演算法中，我們將執行一個過程，該過程使用不同的函式來統計字串的不同迴文特性，這些函式檢查給定字串的子串str[i..j]是否為迴文。使用此演算法，我們將構建一些C++語法來有效地學習問題陳述。
步驟1 - 開始程序。
步驟2 - 宣告輸入輸出流。
步驟3 - 匯入內建類和宣告的函式。
步驟4 - 宣告for迴圈並迭代過程。
步驟5 - 如果條件滿足，則列印true。
步驟6 - 否則，列印false。
步驟7 - 追加元素。
步驟8 - 刪除最後一個元素。
步驟9 - 檢查差異。
步驟10 - 獲取結果並終止程序。
統計字串迴文字元的語法
Initial Values : i = 0, j = n-1;
Given string 'str'
CountPS(i, j)
If (j == i+1)
return str[i] == str[j]
Else if(i == j || i > j) return 0;
Else If str[i..j] is Palindrome Number
return countPS(i+1, j) + countPS(i, j-1) + 1 -
countPS(i+1, j-1);
Else
return countPS(i+1, j) + countPS(i, j-1) -
countPS(i+1 , j-1);
在上述可能的語法中，我們嘗試向您展示如何執行統計字串的不同迴文特性的過程，方法是使用不同的函式來檢查給定字串的子串str[i..j]是否為迴文。透過使用此語法，我們將朝著一些已知的有效解決問題陳述的方法前進。
遵循的方法
方法1 - 使用countKPalindromes()、memset()和C++環境中的二維矩陣來統計字串的迴文特性。
方法2 - 使用遞迴函式以及奇數和偶數字符、布林字串和重疊子問題來查詢字串迴文子串的C++程式
方法1：使用CountKPalindromes()、Memset()和二維矩陣
CountKPalindromes()方法的使用
在這種可能的方法中，我們將應用countKPalindromes()方法來統計字串的迴文特性。
int n = temp.length();
for (int i = 0; i < n/ 2; i++) {
if (temp[i] != temp[n - i - 1]) {
return false;
}
}
return true;
int main(){
string s;
cin>>s;
int mxlength = 0;
int n = s.length();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
string temp = s.substr(i,j-i+1);
if(isPalindrome(temp)){
int len = j-i+1;
mxlength = max(mxlength,len);
}
}
}
int cnt=0;
for(int i=0;i<=n-mxlength;i++){
string temp = s.substr(i,mxlength);
if(isPalindrome(temp)){
cnt++;
}
}
cout<<mxlength<<" "<<cnt<<endl;
示例
//A C++ program which counts different palindromic characteristics of a string by using a function which checks whether a substring str[i..j] of a given string is a palindrome or not.
#include <bits/stdc++.h>
using namespace std;
const int MAX_STR_LEN = 1000;
bool P[MAX_STR_LEN][MAX_STR_LEN];
int Kpal[MAX_STR_LEN];
void checkSubStrPal(string str, int n){
memset(P, false, sizeof(P));
for (int i = 0; i < n; i++)
P[i][i] = true;
for (int i = 0; i < n - 1; i++)
if (str[i] == str[i + 1])
P[i][i + 1] = true;
for (int gap = 2; gap < n; gap++){
for (int i = 0; i < n - gap; i++){
int j = gap + i;
if (str[i] == str[j] && P[i + 1][j - 1])
P[i][j] = true;
}
}
}
void countKPalindromes(int i, int j, int k){
if (i == j){
Kpal[k]++;
return;
}
if (P[i][j] == false)
return;
Kpal[k]++;
int mid = (i + j) / 2;
if ((j - i + 1) % 2 == 1)
mid--;
countKPalindromes(i, mid, k + 1);
}
void printKPalindromes(string s){
memset(Kpal, 0, sizeof(Kpal));
int n = s.length();
checkSubStrPal(s, n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n - i; j++)
countKPalindromes(j, j + i, 1);
for (int i = 1; i <= n; i++)
cout << Kpal[i] << " ";
cout << "\n";
}
int main(){
string s = "abacaba";
printKPalindromes(s);
return 0;
}
輸出
12 4 1 0 0 0 0
Memset()方法的使用
在這種可能的方法中，我們將應用memset()方法來統計字串的迴文特性。
示例
// C++ program to find palindromic substrings of a string which returns total number of palindrome substring of length greater than equal to 2
#include <bits/stdc++.h>
using namespace std;
int CountPS(char str[], int n){
int ans=0;
bool P[n][n];
memset(P, false, sizeof(P));
for (int i = 0; i < n; i++){
P[i][i] = true;
}
for (int gap = 2; gap <=n; gap++){
for (int i = 0; i <= n-gap; i++){
int j = gap + i-1;
if(i==j-1){
P[i][j]=(str[i]==str[j]);
} else{
P[i][j]=(str[i]==str[j] && P[i+1][j-1]);
}
if(P[i][j]){
ans++;
}
}
}
return ans;
}
int main(){
char str[] = "abaab";
int n = strlen(str);
cout << CountPS(str, n) << endl;
return 0;
}
輸出
3
二維矩陣的使用
在這種可能的方法中，我們將構造和應用二維矩陣來統計字串的迴文特性。
示例
//C++ program to find palindromic substrings of a string by using a 2D matrix
#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
bool isPal(string s, int i, int j){
if (i > j)
return 1;
if (dp[i][j] != -1)
return dp[i][j];
if (s[i] != s[j])
return dp[i][j] = 0;
return dp[i][j] = isPal(s, i + 1, j - 1);
}
int countSubstrings(string s){
memset(dp, -1, sizeof(dp));
int n = s.length();
int count = 0;
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
if (isPal(s, i, j))
count++;
}
}
return count;
}
int main(){
string s = "abbaeae";
cout << countSubstrings(s);
return 0;
}
輸出
4
方法2：使用遞迴函式以及奇數和偶數字符、布林字串和重疊子問題
布林字串方法的使用
在這種可能的方法中，我們將構造和應用布林字串來統計字串的迴文特性。
int n = temp.length();
for (int i = 0; i < n/ 2; i++) {
if (temp[i] != temp[n - i - 1]) {
return false;
}
}
return true;
}
int maxLengthOfPalindromicSubstring(string s) {
int length = 0;
int len = 0;
if (s.size() == 2 and s[0] == s[1]) {
return 2;
} else if (s.size() < 3) {
string c(1, s[0]);
return 1;
}
string temp;
for (int i = 0; i < s.size() - 1; i++) {
len = 0;
while ((i-len) >= 0 and (i+1+len) < s.size() and s[i-len] ==
s[i+1+len]) {
if (length < 2*len+2){
length = 2*len+2;
temp = s.substr(i-len, length);
}
len++;
}
len = 0;
while ((i-len >= 0) and (i+len < s.size()) and s[i-len] == s[i+len]) {
if (length < 2*len+1) {
length = 2*len+1;
temp = s.substr(i-len, length);
}
len++;
}
}
return temp.length();
}
int main(){
string s;
cin>>s;
int n = s.length();
int mxlength = maxLengthOfPalindromicSubstring(s);
int cnt=0;
for(int i=0;i<=n-mxlength;i++){
string temp = s.substr(i,mxlength);
if(isPalindrome(temp)){
cnt++;
}
}
cout<<mxlength<<" "<<cnt<<endl;
示例
//C++ program to find palindromic substrings of a string by using the boolean string
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string s){
for (int i = 0; i < s.length(); ++i) {
if (s[i] != s[s.length() - i - 1]) {
return false;
}
}
return true;
}
bool ans(string s){
string s2 = s;
for (int i = 0; i < s.length(); ++i){
s2 = s2.back() + s2;
s2.pop_back();
if (s != s2 && isPalindrome(s2)) {
return true;
}
}
return false;
}
int solve(string s){
if (s.length() <= 3) {
return -1;
}
int cnt[25] = {};
for (int i = 0; i < s.length(); i++) {
cnt[s[i] - 'a']++;
}
if (*max_element(cnt, cnt + 25) >= (s.length() - 1)) {
return -1;
} else {
return (ans(s) ? 1 : 2);
}
}
int main(){
string s = "arbrdd";
cout << solve(s);
return 0;
}
輸出
2
使用具有奇數和偶數字符的遞迴函式方法
在這種可能的方法中，我們將使用具有奇數和偶數字符的遞迴函式來構造和應用字串以統計迴文特性。
示例
//C++ program to find palindromic substrings of a string by using recursive function with odd and even characters
#include <bits/stdc++.h>
using namespace std;
int solveEven(string s){
if (s.length() % 2 == 1)
return 2;
string ls = s.substr(0, s.length() / 2);
string rs = s.substr(s.length() / 2, s.length());
if (ls != rs)
return 1;
return solveEven(ls);
}
int solveOdd(string s){
return 2;
}
int solve(string s){
if (s.length() <= 3) {
return -1;
}
int cnt[25] = {};
for (int i = 0; i < s.length(); i++){
cnt[s[i] - 'a']++;
}
if (*max_element(cnt, cnt + 25) >= s.length() - 1){
return -1;
}
if (s.length() % 2 == 0)
return solveEven(s);
if (s.length() % 2 == 1)
return solveOdd(s);
}
int main(){
string s = "ARBRDD";
cout << solve(s);
return 0;
}
輸出
1
重疊子問題方法的使用
在這種可能的方法中，我們將使用重疊子問題來應用字串以在C++環境中統計迴文特性。
示例
//C++ program to find palindromic substrings of a string by using Overlapping Subproblems
#include <cstring>
#include <iostream>
using namespace std;
int countPS(string str){
int N = str.length();
int cps[N + 1][N + 1];
memset(cps, 0, sizeof(cps));
for (int i = 0; i < N; i++)
cps[i][i] = 1;
for (int L = 2; L <= N; L++) {
for (int i = 0; i <= N-L; i++) {
int k = L + i - 1;
if (str[i] == str[k])
cps[i][k]
= cps[i][k - 1] + cps[i + 1][k] + 1;
else
cps[i][k] = cps[i][k - 1] + cps[i + 1][k]
- cps[i + 1][k - 1];
}
}
return cps[0][N - 1];
}
int main(){
string str = "arbrdd";
cout << "Total palindromic character sequence are present here : "
<< countPS(str) << endl;
return 0;
}
輸出
Total palindromic character sequence are present here is : 9
結論
今天在這篇文章中，我們學習瞭如何在C++環境中實現統計字串的不同迴文特性的過程，方法是使用一個函式來檢查給定字串的子串str[i..j]是否為迴文。透過以上提到的邏輯、語法和演算法，我們嘗試構建一些C++程式碼來有效地解決問題陳述。
更新於：2023年12月27日
瀏覽量：57
廣告