数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
