สมมติว่าเราได้กำหนดความยาวของสตริง 'str' และสตริง ภารกิจคือการนับจำนวนสตริงย่อยที่ขึ้นต้นด้วย '1' และลงท้ายด้วย '1' ใน Binary String ที่กำหนด สตริงไบนารีประกอบด้วย '1' และ '0' เท่านั้น ตัวอย่างเช่น
อินพุต-1 −
N = 5 str = ‘11101’
ผลผลิต −
6
คำอธิบาย − ใน Binary String ที่กำหนด เรามี 6 สตริงย่อยที่ขึ้นต้นด้วย '1' และลงท้ายด้วย '1' ชุดของสตริงย่อยเหล่านี้คือ {'11', '111', '1110', '11101', '1101', '101'}
อินพุต-1 −
N = 4 str = ‘0011’
ผลผลิต −
1
คำอธิบาย −
ใน Binary String ที่กำหนด เรามี 1 สตริงย่อยที่ขึ้นต้นด้วย '1' และลงท้ายด้วย '1' ชุดของสตริงย่อยเหล่านี้เป็นชุดซิงเกิลตัน เช่น { '11 '}.
แนวทางที่ใช้ในการแก้ปัญหานี้
สำหรับสตริงที่กำหนด เราต้องนับจำนวนสตริงย่อยที่ขึ้นต้นด้วย "1" และลงท้ายด้วย "1" ปัญหานี้คล้ายกับปัญหา Handshake ที่รู้จักกันดี ซึ่งเราต้องนับจำนวนการจับมือในปาร์ตี้ของคน 'n'
หากเรานับจำนวน 1 ในสตริงที่กำหนด เราจะพบชุดของสตริงย่อยที่ขึ้นต้นด้วย "1" และลงท้ายด้วย "1"
-
รับอินพุตสตริงที่มีความยาว N
-
ฟังก์ชัน Integer countSubstring(int N, string s) ใช้ความยาวของสตริงและสตริงเป็นอินพุต และส่งคืนค่าจำนวนสตริงย่อยทั้งหมดที่ขึ้นต้นด้วย '1' และลงท้ายด้วย '1'
-
วนซ้ำตลอดทั้งสตริงและนับจำนวน ของ '1' ในสตริง
-
นับเลขที่ ของสตริงย่อย (คู่) ในสตริงที่กำหนดโดย n*(n-1)/2.
-
ส่งกลับผลลัพธ์ของ n*(n-1)/2.
ตัวอย่าง
#include<iostream>
using namespace std;
int countSubstring(int N, string s){
int count=0;
for(int i=0; s[i]!= '\0'; ++i){
if( s[i]== '1' )
count++;
}
return count*(count-1)/2;
}
int main() {
int N=5;
string str= "11101";
cout<< countSubstring(N,str)<<endl;
return 0;
} ผลลัพธ์
หากเราจะเรียกใช้โค้ดข้างต้น มันจะพิมพ์ผลลัพธ์เป็น,
6
เนื่องจากจำนวน '1' ที่มีอยู่ในสตริงที่กำหนดคือ '4' เช่น count =4 จำนวนทั้งหมดของสตริงย่อยที่ขึ้นต้นด้วย '1' และลงท้ายด้วย '1' คือ 4*(4-1)/2 =6.
