Cari subrentetan pariti ganjil terpanjang

Pengenalan

Dalam tutorial ini, kami membangunkan kaedah untuk mencari subrentetan pariti ganjil panjang maksimum. Pariti ganjil dalam subrentetan bermakna 1 diulang beberapa kali ganjil dalam rentetan. Pariti dalam C++ mentakrifkan nombor set bit dan 1 dalam nombor. Terdapat dua jenis pariti: pariti genap dan pariti ganjil.

Apabila jumlah bilangan "1" dalam perwakilan binari adalah ganjil, ia dipanggil rentetan pariti ganjil. Dalam tutorial ini, kami menggunakan konsep pengaturcaraan C++ untuk mencari subrentetan pariti ganjil panjang maksimum.

Pelaksanaan 1

String = 101100

Output = 6

Dalam contoh di atas, panjang subrentetan pariti ganjil maksimum ialah 6, dan subrentetan boleh 011100. Jumlah bilangan 1 dalam subrentetan ini ialah 3, iaitu nombor ganjil. Jadikannya subrentetan pariti ganjil.

Pelaksanaan 2

String = 1011010

Output = 6

Dalam contoh di atas, panjang maksimum subrentetan pariti ganjil dalam rentetan yang diberikan ialah 6. Subrentetan yang mungkin boleh jadi 011010 kerana ia mengandungi sejumlah 3 "1", menjadikannya subrentetan pariti ganjil.

Algoritma

• Buat pembolehubah pembilang ct untuk mengira 1 dalam rentetan input.

• Jika ct = 0, subrentetan pariti ganjil tidak boleh dibentuk kerana rentetan input hanya mengandungi 0.

• Jika jumlah bilangan 1 dalam rentetan input adalah ganjil, panjang subrentetan adalah sama dengan panjang rentetan itu.

• Apabila nilai pembolehubah ct ialah nombor genap, subrentetan boleh terdiri daripada dua kemungkinan.

• Cari subrentetan pariti ganjil terpanjang.

• Panjang cetakan.

Contoh

Kami melaksanakan contoh 2 dalam C++ dan menggunakan fungsi length() kelas rentetan untuk mencari panjang rentetan input dan subrentetan yang terhasil.

#include <bits/stdc++.h>
using namespace std;
 
// user defined function for calculating the index value of string
int indexOfString(string st, char ch, int j){
   for(; j < st.length(); j++)
      if(st[j] == ch)
      return j;      
      return -1;
}
//finding the lsat index value of the string
int lastIndexOfString(string st,char ch,int j){
   for(; j >= 0; j--)
      if(st[j] == ch)
   return j;
   return -1;
}
 
//user defined function to find the length of the longest odd parity substring
int maxSubstring(string s, int l){

   //variable for counting 1s
   int ct = 0;
   for (int j = 0; j < l; j++)
      if (s[j] == '1')
         ct++;

   //different counter variable conditions
   if (ct == 0)
      return 0;
       
   if (ct % 2 == 1)
      return l;
       
   int firstTime = indexOfString(s,'1',0);
   int secondTime = indexOfString(s,'1', firstTime + 1);

   int lastTime = lastIndexOfString(s,'1',s.length()-1);
   int secondLastTime = lastIndexOfString(s,'1', lastTime - 1);

   return max(lastTime, l - firstTime - 1);
}

// Controller
int main(){
   string s = "1011010";
   int l = s.length();
   cout<<"The maximum length of the odd parity substring is:" <<(maxSubstring(s, l));
}

Output

The maximum length of the odd parity substring is: 6

Kesimpulan

Dalam tutorial ini, kami membangunkan kaedah untuk mencari panjang subrentetan ganjil-genap terpanjang daripada rentetan input yang diberikan. Panjang subrentetan pariti ganjil dikira menggunakan pembolehubah pembilang dan menentukan berbeza jika syarat untuknya.

Kami menggunakan fungsi length() kelas rentetan untuk membantu mencari panjang subrentetan dan nilai indeks rentetan input. Nilai indeks menjana subrentetan.

Atas ialah kandungan terperinci Cari subrentetan pariti ganjil terpanjang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!