ศูนย์ต่อเนื่องสูงสุดในสตริงไบนารีที่ต่อกันใน C ++

สมมติว่าเรามีสตริงไบนารีที่มีความยาว n ค่าอื่นคือ k ที่ให้มา เราต้องต่อสตริงไบนารี k ครั้ง จากนั้นเราต้องหาจำนวนสูงสุดของ 0s ที่ต่อเนื่องกันในสตริงที่ต่อกัน สมมติว่าสตริงไบนารีคือ "0010010" และ k =2 จากนั้นหลังจากต่อสตริง k ครั้งแล้ว สตริงจะเป็น "00100100010010" ดังนั้นจำนวนสูงสุดของ 0s ติดต่อกันคือ 3

วิธีการนั้นง่าย หากตัวเลขมี 0 ทั้งหมด คำตอบจะเป็น n * k หากสตริงประกอบด้วยสตริง ผลลัพธ์จะเป็นความยาวสูงสุดของสตริงย่อยของสตริง ที่มี 0 ทั้งหมด หรือผลรวมระหว่างความยาวของคำนำหน้าสูงสุดของสตริงที่มีเพียง 0 วินาที และความยาวของส่วนต่อท้ายสูงสุดของ สตริงที่มีเพียง 0s.

อัลกอริทึม

max_zero_count (str, n, k) −

Begin
total := 0
len := 0
for i in range 0 to n, do
   if str[i] = 0, then increase len
   else len := 0
   total := maximum of total and len
done
if total = n, then return n * k
prefix := length of maximal prefix with only 0
suffix:= length of maximal suffix with only 0
if k > 1, then
   total := max of total, and (prefix + suffix)
return total
End

ตัวอย่าง

#include <iostream>
using namespace std;
int max_length_substring(string str, int n, int k) {
   int total_len = 0;
   int len = 0;
   for (int i = 0; i < n; ++i) {
      if (str[i] == '0') //if the current character is 0, increase len
         len++;
      else
         len = 0;
      total_len = max(total_len, len);
   }
   if (total_len == n) //if the whole string has 0 only
      return n * k;
   int prefix = 0, suffix = 0;
   for (int i = 0; str[i] == '0'; ++i, ++prefix) //find length of maximal prefix with only 0;
   for (int i = n - 1; str[i] == '0'; --i, ++suffix) //find length of maximal suffix with only 0;
   if (k > 1)
      total_len = max(total_len, prefix + suffix);
   return total_len;
}
int main() {
   int k = 3;
   string str = "0010010";
   int res = max_length_substring(str, str.length(), k);
   cout << "Maximum length of 0s: " << res;
}

ผลลัพธ์

Maximum length of 0s: 3