資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++中包含字元X至少一次的子字串計數
給定一個字串str[]和一個字元X。目標是找到str[]的子字串，使得所有子字串都至少包含X一次。例如，對於str[]=”abc”和X=’a’，至少包含’a’一次的子字串是“a”、“ab”、“abc”。計數為3。
讓我們透過例子來理解。
輸入 − str[] = “aabccd” X=’c’
輸出 − 至少包含字元X一次的子字串計數為− 14
解釋 − 包含至少一個’c’的子字串為：“c”、“cc”、“cd”、“bc”、“bcc”、“ccd”、“abc”、“abcc”、“bccd”、“aabc”、“aabcc”、“abccd”、“aabccd”。
輸入 − str[] = “settings” X=’s’
輸出 − 至少包含字元X一次的子字串計數為− 14
解釋 − 包含至少一個’s’的子字串為：“s”, "se", "set", "sett", "setti", "setting", "settings", "gs", "ngs", "ngs", "sett", "tings", "setting", "ettings", "settings"
下面程式中使用的演算法如下
在這個演算法中，我們知道具有n個字元的字串的子字串總數為n*(n+1)/2。
我們現在將遍歷字串並計算字元X之前的字元數作為temp。一旦遇到X，包含X的字串長度將為temp+1。現在我們有X個包含X的子字串將是剩餘字元（長度-當前索引）X（temp+1）。將此新增到計數中。現在將temp更新為0，並繼續進行下一個X，直到字串結束。最後，我們將計數作為至少包含字元X一次的子字串的數量。
取一個字串str和一個字元x。
函式sub_x(char str[],int length,char x)接受一個字串、它的長度、字元x並返回至少包含字元x一次的子字串的計數。
將初始計數設定為0。將temp作為str[]中第一個x之前的字元數，初始設定為0。
將初始計數設定為size*(size+1)/2，表示str[]所有可能的子字串的數量。
使用for迴圈遍歷str[]，從i=0到i<size。
如果str[i]不是x，則將temp遞增，表示第一個x之前的字元數。
如果str[i] == x，則包含x的字串長度將為temp+1。str[]的剩餘字元將為length-i。
所有子字串將為(temp+1) * (length-i)。將此新增到計數中。現在將temp更新為0，用於下一次迭代。
執行此操作直到到達str[]的末尾。
最後返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int sub_x(string str, int length, char x){
int count = 0;
int temp = 0;
for (int i = 0; i < length; i++){
if (str[i] == x){
int temp_2 = temp + 1;
count = count + temp_2 * (length - i);
temp = 0;
}
else{
temp++;
}
}
return count;
}
int main(){
string str = "abcabbc";
int length = str.length();
char x = 'a';
cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length,
x);
return 0;
}輸出
如果我們執行上面的程式碼，它將生成以下輸出：
Count of sub-strings that contain character X at least once are: 19
250 次瀏覽
