資料結構
網路
關係資料庫管理系統 (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 次瀏覽
