Kira bilangan subrentetan panjang M yang muncul tepat K kali dalam rentetan

Dalam artikel ini, kita akan menyelidiki masalah unik dan menarik dalam bidang sains komputer - "Kira subrentetan panjang M yang berlaku tepat K kali dalam rentetan". Soalan jenis ini sering ditanya dalam pertandingan pengaturcaraan dan temuduga. Sebelum kita mula, mari kita tentukan perkara yang kita hadapi -

• Substring− Urutan bersebelahan yang terdapat dalam rentetan lain.

• M length− Panjang substring yang kami minati.

• K kali − Bilangan tepat subrentetan harus muncul dalam rentetan asal.

Penerangan algoritma

Untuk menyelesaikan masalah ini, kami akan memanfaatkan kuasa peta cincang (juga dipanggil peta tidak tertib dalam C++). Peta hash membolehkan kami menyimpan data dalam bentuk pasangan nilai kunci dan menyediakan kerumitan masa yang berterusan untuk operasi carian dan sisipan, menjadikannya alat yang sangat baik untuk menyelesaikan masalah sedemikian.

Algoritma untuk mengira subrentetan panjang M yang muncul tepat K kali dalam rentetan adalah seperti berikut -

• Mulakan peta cincang kosong.

• Lelaran pada rentetan, mencipta semua subrentetan panjang M yang mungkin.

• Untuk setiap subrentetan, tambahkannya pada peta cincang. Jika ia sudah wujud, tingkatkan bilangannya.

• Selepas semua subrentetan dikira, ulangi peta cincang untuk mencari semua subrentetan yang berlaku tepat K kali.

Pelaksanaan C++

Ini ialah pelaksanaan C++ bagi algoritma di atas -

Contoh

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string s, int M, int K) {
   unordered_map<string, int> count_map;
   int n = s.length();
   
   for (int i = 0; i <= n - M; i++) {
      string substring = s.substr(i, M);
      count_map[substring]++;
   }
   
   int count = 0;
   for (auto it : count_map) {
      if (it.second == K)
         count++;
   }

    return count;
}

int main() {
   string s = "abcabcabc";
   int M = 3;
   int K = 3;
   
   int result = countSubstrings(s, M, K);
   cout << "The number of M-length substrings occurring exactly K times is: " << result << endl;
   
   return 0;
}

Output

The number of M-length substrings occurring exactly K times is: 1

Dalam kod di atas, fungsi countSubstrings mengambil rentetan input s, panjang subrentetan M dan bilangan kejadian K sebagai parameter. Ia memulakan count_map peta tidak tertib untuk menjejaki semua subrentetan dan kejadiannya. Ia kemudian melelang ke atas rentetan untuk mencipta semua kemungkinan subrentetan panjang M, dan untuk setiap subrentetan ia menambah kiraan dalam peta. Sebaik sahaja semua subrentetan telah dikira, ia berulang pada peta untuk mengira semua subrentetan yang berlaku tepat K kali.

Fungsi utama ialah di mana pelaksanaan kod bermula. Ia memulakan rentetan s dan nilai M dan K. Kemudian panggil fungsi countSubstrings dan cetak hasilnya.

Contoh kes ujian

Mari kita pertimbangkan rentetan "abcabcabc" di mana M=3 dan K=3.

Di sini, subrentetan panjang M ialah "abc", "bca", "cab", "abc", "bca", "cab", "abc". Jelas sekali, subrentetan "abc" berlaku tepat 3 kali dalam rentetan, jadi output program adalah 1.

Pendekatan kepada masalah ini, di mana kami menggunakan peta cincang untuk mengira subrentetan, ialah contoh yang baik bagi pertukaran ruang-masa dalam sains komputer. Apabila kami menggunakan ruang tambahan untuk menyimpan subrentetan dan kiraannya, kami boleh mengurangkan kerumitan masa masalah dengan ketara dengan mengira kejadian dalam masa tetap.

Kerumitan masa dan ruang

Kerumitan masa algoritma ini ialah O(n), dengan n ialah panjang rentetan. Ini kerana kami mengulangi rentetan sekali sahaja untuk mencipta semua subrentetan panjang M yang mungkin.

Disebabkan keperluan penyimpanan peta cincang, kerumitan ruang juga O(n), dalam kes yang paling teruk, setiap subrentetan adalah unik, menghasilkan n entri berbeza dalam peta.

Kesimpulan

Dalam artikel ini, kami mengkaji masalah biasa dalam sains komputer - mengira bilangan subrentetan panjang M yang berlaku tepat K kali dalam rentetan. Kami melaksanakan penyelesaian yang cekap dalam C++ menggunakan peta cincang, yang memberikan kami operasi carian dan sisipan masa yang berterusan. Masalah ini ialah contoh sempurna bagaimana struktur data dan algoritma boleh digunakan bersama untuk menyelesaikan masalah kompleks dengan berkesan.

Atas ialah kandungan terperinci Kira bilangan subrentetan panjang M yang muncul tepat K kali dalam rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!