数据结构
网络
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 次浏览
