मान लीजिए कि एक स्ट्रिंग में 1(0+)1 जैसे पैटर्न हैं। जहां (0+) 1s की गैर-रिक्त लगातार घटनाओं को इंगित करता है। हमें सभी पैटर्न खोजने होंगे। पैटर्न ओवरलैप कर सकते हैं। स्ट्रिंग जरूरी नहीं कि एक बाइनरी स्ट्रिंग हो। यह केवल अंक और लोअरकेस वर्ण धारण कर सकता है। मान लीजिए कि स्ट्रिंग 1101001 की तरह है, तो ऐसे दो पैटर्न हैं। 101 और 1001.
इस समस्या को हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
स्ट्रिंग में सभी वर्ण c के माध्यम से पुनरावृति करें
-
जब c 1 होता है, तब हम तब तक पुनरावृति करते हैं जब तक कि तत्व 0
. न हो जाए -
जब 0 की धारा समाप्त हो जाती है, तो हम जांचेंगे कि अगला वर्ण 1 है या नहीं
-
स्ट्रिंग के अंत तक इन चरणों को दोहराया जाएगा।
उदाहरण
#include<iostream>
using namespace std;
int countBinPattern(string main_str) {
char last_char = main_str[0];
int i = 1, counter = 0;
while (i < main_str.size()) {
if (main_str[i] == '0' && last_char == '1') {
while (main_str[i] == '0')
i++;
if (main_str[i] == '1')
counter++;
}
last_char = main_str[i];
i++;
}
return counter;
}
int main() {
string str = "10010110000101";
cout << "Number of substrings of pattern 1(0+)1 is: " << countBinPattern(str);
} आउटपुट
Number of substrings of pattern 1(0+)1 is: 4