数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中统计首尾字符相同的子字符串个数
给定一个字符串str，目标是统计str中首尾字符相同的子字符串个数。例如，如果输入是“baca”，子字符串将是“b”、“a”、“c”、“a”、“aca”。总共5个。
让我们通过例子来理解。
输入 − str=”abaefgf”
输出 −首尾字符相同的子字符串个数为：9
解释 − 子字符串将是……
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
输入 − str=”abcdef”
输出 −首尾字符相同的子字符串个数为：6
解释 − 子字符串将是……
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
下面程序中使用的方法如下
解决给定问题有多种方法，即朴素方法和高效方法。所以让我们首先看看朴素方法。我们将把每个长度的子字符串传递给函数check()。如果该子字符串的开头和结尾字符相同，则递增计数。
取字符串str。计算长度为str.size()。
函数check(string str)接受子字符串str，并检查其首尾字符是否相同 (str[0]==str[length-1])。如果相同，则返回1。
函数check_Start_End(string str, int length)接受str及其长度作为输入，并返回str中首尾字符相同的子字符串个数。
将初始计数设置为0。
使用两个for循环遍历str。从i=0到i<length，内部循环j=1到j=length-1。
我们将使用substr(i,j)获取所有长度的子字符串。将每个子字符串传递给check()。如果它返回1，则递增计数。
在两个for循环结束时，count将包含str中首尾字符相同的子字符串个数。
返回count作为所需结果。
高效方法
我们可以看到，答案取决于原始字符串中每个字符的频率。
例如，在“bacba”中，“b”的频率为2，包含“b”的子字符串为“b”、“bacb”和“b”。
即2+1C2=3。我们将首先检查每个字符的频率，并添加(字符频率+1)C2。
取字符串str。计算长度为str.size()。
函数check_Start_End(string str, int length)接受str及其长度作为输入，并返回str中首尾字符相同的子字符串个数。
取初始计数-0。
取一个数组arr[26]来存储每个字符的频率。
遍历字符串并将频率存储到arr[str[i]=’a’]++中。
遍历频率数组arr[26]，对于每个频率arr[i]，添加arr[i]*(arr[i]+1)/2到计数中。
最后返回计数作为结果。
示例（朴素方法）
#include <bits/stdc++.h>
using namespace std;
int check(string str){
int length = str.length();
if(str[0] == str[length-1]){
return 1;
}
}
int check_Start_End(string str, int length){
int count = 0;
for (int i = 0; i < length; i++){
for (int j = 1; j <= length-i; j++){
if (check(str.substr(i, j))){
count++;
}
}
}
return count;
}
int main(){
string str = "bcbdedfef";
int length = str.length();
cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str, length);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of substrings with same first and last characters are: 13
示例（高效方法）
#include <bits/stdc++.h>
using namespace std;
#define maximum 26
int check_Start_End(string str, int length){
int count = 0;
int arr[maximum] = {0};
for(int i=0; i<length; i++){
arr[str[i] - 'a']++;
}
for (int i=0; i<maximum; i++){
count = count + (arr[i]*(arr[i]+1)/2);
}
return count;
}
int main(){
string str = "bcbdedfef";
int length = str.length();
cout<<"Count of substrings with same first and last characters are: "<<check_Start_End(str,
length);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count of substrings with same first and last characters are: 13
446 次浏览
