数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中所有回文子串的计数
给定一个字符串 str[] 作为输入。目标是计算 str[] 中存在的回文子串的数量。如果两个字符串包含相同数量的字符并且所有字符都出现在两者中，则它们互为回文。字符的顺序可以不同。
“abc” 是 “cba”、 “bca” 等的回文。
让我们通过示例来理解。
输入 − str[] = “abccb”
输出 − 回文子串的总数为 − 4
解释 − 回文为 − (b,b), (c,c), (bc,cb), (bcc,ccb)
输入 − str = “aaa”
输出 − 回文子串的总数为 − 4
解释 − 回文为 − (a,a), (a,a), (a,a), (aa,aa)
下面程序中使用的方案如下
我们使用一个包含向量的映射，其中向量包含子字符串中英文字母的频率以及数组中此类子字符串的计数。在 map<vector<int>, int> mp_vec; 中，vector<int> vec(MAX, 0) 将存储当前子字符串中所有 26 个字母的频率。映射的整数将是具有相同频率向量的此类子字符串的计数。对于每个子字符串，如果回文的计数为 x。那么回文对的总数将为 x*(x-1)/2。
将字符串 str[] 作为字符数组。
函数 anagram_substring(string str, int length) 获取字符串并返回回文子串的总数。
将初始计数设置为 0。
创建一个映射，map<vector<int>, int> mp_vec;
使用两个 for 循环遍历 str[]，从 i=0 到 i<length，以及 j=i 到 j<length。
对于每个子字符串 str[i 到 j]。vector<int> vec(MAX, 0); 将包含其中英文字母的计数。
将当前字符作为 c 作为 str[j]。通过 temp=c-’a’ 获取其整数值。
使用 vec[temp]++ 更新频率。
使用 mp_vec[vec]++ 增加对应于此频率向量的计数。
现在遍历包含所有频率向量的映射，并使用 for 循环从迭代器 it=mp_vec.begin() 到 it != mp_vec.end() 聚合子字符串计数。
对于每个计数作为 it->second，将 ((last) * (last-1))/2 添加到所有回文对的计数中
最后，我们将获得所有回文的计数。
返回计数作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
int anagram_substring(string str, int length){
int count = 0;
map<vector<int>, int> mp_vec;
for (int i=0; i<length; i++){
vector<int> vec(MAX, 0);
for (int j=i; j<length; j++){
char c = str[j];
char temp = c - 'a';
vec[temp]++;
mp_vec[vec]++;
}
}
for (auto it = mp_vec.begin(); it != mp_vec.end(); it++){
int last = it->second;
count += ((last) * (last-1))/2;
}
return count;
}
int main(){
string str = "TP";
int length = str.length();
cout<<"Count of total anagram substrings are: "<<anagram_substring(str, length) << endl;
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of total anagram substrings are: 3
665 次浏览
