資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中不包含集合 {‘a’, ‘b’, ‘c’} 中所有字元的子字串的計數
給定一個字串 str[]，其中只包含 ‘a’，‘b’ 和 ‘c’。目標是找到 str[] 的子字串，使得所有三個字元都不屬於該子字串。對於任何字串 str，子字串可以是“a”、“b”、“c”、“abb”、“bba”、“bc”、“ca”、“ccc”，但不能是“abc”、“bcca”、“cab”，因為這些子字串包含了 ‘a’，‘b’ 和 ‘c’ 這三個字元。
讓我們透過例子來理解。
輸入 − str[] = “aabc”
輸出 − 不包含集合 {‘a’, ‘b’, ‘c’} 中所有字元的子字串的計數為 − 8
解釋 − 子字串將是：“a”、“a”、“b”、“c”、“aa”、“ab”、“bc”、“aab”
輸入 − str[] = “abcabc”
輸出 − 不包含集合 {‘a’, ‘b’, ‘c’} 中所有字元的子字串的計數為 − 11
解釋 − 子字串將是：“a”、“b”、“c”、“a”、“b”、“c”、“ab”、“bc”、“ca”、“ab”、“bc”
下面程式中使用的方案如下
在這種方案中，我們知道具有 n 個字元的字串的子字串總數為 n*(n+1)/2。
我們現在將遍歷字串，並針對每種型別的字元 ‘a’，‘b’ 或 ‘c’。我們將檢查其他兩個字元 (‘b’,’c’)、(‘c’,’a’) 和 (‘a’, ‘b’) 的先前索引。只需從計數中減去其他兩個字元的最小索引，因為我們知道我們正在移除該字元以在子字串中包含當前字元，以便它不包含所有三個字元。
將字串 str 作為字元陣列。
函式 sub_without_all(char str[], int size) 獲取一個字串，它的長度並返回不包含 ‘a’，‘b’ 和 ‘c’ 所有字元的子字串的計數。
獲取初始計數 size*(size+1)/2，表示 str[] 所有可能的子字串的數量。
獲取變數 a、b、c 以儲存 str[] 中 ‘a’，‘b’，‘c’ 的最後一個索引。全部初始化為 0。
使用 for 迴圈遍歷 str[]，從 i=0 到 i<size。
如果 str[i]==’a’，則將 ‘a’ 的索引更新為 a=i+1。從計數中減去 ‘b’ 或 ‘c’ 的最小索引以在子字串中包含 ‘a’。從計數中減去 b、c 中較小的一個。
對 str[i]==’b’ 或 str[i]==’c’ 執行與上一步類似的操作。
最後，我們得到計數，表示 str[] 中不包含所有三個字元的子字串的數量。
返回計數作為結果。
示例
#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
int update_size = size * (size + 1);
int count = update_size / 2;
int a, b, c;
a = b = c = 0;
for (int i = 0; i < size; i++){
if (str[i] == 'a'){
a = i + 1;
count -= min(b, c);
}
else if (str[i] == 'b'){
b = i + 1;
count -= min(a, c);
}
else{
c = i + 1;
count -= min(a, b);
}
}
return count;
}
int main(){
char str[] = "abcabbc";
int size = strlen(str);
cout<<"Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at
the same time are: "<<sub_without_all(str, size);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of sub-strings that do not contain all the characters from the set {‘a’, ‘b’, ‘c’} at the same time are: 15
210 次瀏覽
