資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學給定二進位制字串中的不重疊子串“101”和“010”的計數
二進位制字串是一個僅由 0 和 1 組成字元序列。二進位制字串不能包含任何其他字元。二進位制字串的一些示例為 “0000”、“01010”或“11111”。
給定字串的子字串是按順序獲取的一個字元序列。一個字串可能包含多個子字串。不重疊的字串是指任意兩個找到的子字串的索引不能相互衝突。這意味著任意兩個子字串 substr1[a..b] 和 substr2[c..d]，下列情況之一必須為真，b
本問題涉及計算給定字串中與子字串“101”或“010”匹配的子字串。
示例
示例 1 - str： “1010100010101”
輸出 - 4
解釋 - 以下子字串滿足根據本問題提出的條件：-
str[0:2] - 101 str[3:5] - 010 str[7:9] - 010 str[10:12] - 101
上述示例中值得注意的重要一點是，一旦計數了 str[0:2] - 101，子字串 str[1:3] = 010（根據本問題也是有效的子字串）將無法獲取，因為這會導致找到的字串中索引 [1:2] 出現重疊。
用於解決本問題的途徑基於滑動視窗的概念，其中視窗大小保持為等效於要計算的子字串長度。
演算法
步驟 1 − 將二進位制字串作為輸入字串。
步驟 2 − 將輸入字串轉換為字元陣列。
步驟 3 − 維護一個計數器以跟蹤不重疊的字串 “010” 和 “101” 的數量，名稱為 cnt。
步驟 4 − 在字串的長度範圍內進行迭代，直到到達倒數第二個字元。
步驟 5 − 保持為三個的視窗，以將三個索引處的字元與給定的子字串匹配。
步驟 6 − 檢查當前索引字元是否等效於 “0”，下一個是否等效於 “1”，再下一個是否等效於 “0”；或者，檢查當前索引字元是否等效於 “1”，下一個是否等效於 “0”，再下一個是否等效於 “1”。
步驟 7 − 如果任何情況成立，將計數器增加 3，進入下一個視窗。
步驟 8 − 將計數器再增加 1。
步驟 9 − 如果沒有任何情況成立，將計數器增加到下一個位置，以檢查所需子字串。
示例
以下 C++ 程式碼片段演示了在給定字串中找到的不重疊字串的計算過程。
// including the required libraries
#include <iostream>
using namespace std;
//function to count substrings matching the required criteria
int matchstr(string &str){
//counter for storing the number of substrings
int cnt = 0;
//getting the string length
int len = str.length();
//iterating over the string using array indices
for (int i = 0; i < len - 2;) {
//matching the substrings at the specified positions
//if string matches "010"
if (str[i] == '0' && str[i + 1] == '1' && str[i + 2] == '0'){
//incrementing the counter by 3 to get next substring
i += 3;
//increasing the found substrings counter by 1
cnt+=1;
}
//if string matches "101"
else if (str[i] == '1' && str[i + 1] == '0' && str[i + 2] == '1'){
//incrementing the counter by 3 to get next substring
i += 3;
//increasing the found substrings counter by 1
cnt+=1;
} else {
//check for next index
i+=1;
}
}
return cnt;
}
//calling the main function
int main(){
string str = "110100110101";
//returning the count of substrings matching the criteria
int cnt = matchstr(str);
cout<< "The entered String : "<< str;
cout << "\nTotal strings matching :" << cnt;
return 0;
}
輸出
The entered String : 110100110101 Total strings matching :2
說明：有兩個子字串滿足條件，一個是索引位置 str[1:3] = 101，另一個是 str[8:10] = 010。
結論
滑動視窗的概念非常有用，因為它可以方便地用於匹配子字串。視窗的長度保持為要查詢的子字串的長度等效。上述途徑的時間複雜度為 O(n)，其中 n 是字串的長度，因為需要迴圈才能迭代字串字元。上述途徑的空間複雜度為 O(n)，因為字串被強制轉換為由字串的 n 個字元組成的字元陣列。
626 次瀏覽
