数据结构
网络
关系数据库管理系统 (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
广告