计算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（stringstr）接受子字符串str，并检查它的第一个字符和最后一个字符是否相同。（str[0]==str[length-1]）。如果为true，则返回1。
函数check_Start_End（stringstr，intlength）以str及其长度作为输入，并返回以相同字符开头和结尾的str子字符串的计数。
将初始计数设为0。
使用两个for循环遍历str。从i=0到i<length，内部j=1到j=length-1。
我们将使用所有长度的substr(i,j)获得所有子字符串。将每个子字符串传递给check()。如果返回1，则增加计数。
在两个for循环的末尾，count都将包含许多str的子字符串，它们的起始字符和结束字符相同。
返回计数作为期望的结果。
高效的方法
如我们所见，答案取决于原始字符串中每个字符的频率。
例如，在“bacba”中，“b”的频率为2，包括“b”的子字符串为“b”，“bacb”和“b”。
2+1C2=3我们将首先检查每个字符的频率，并添加（char+1的频率）C2。
取字符串str。计算长度为str.size()。
函数check_Start_End（stringstr，intlength）以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