Substring terpanjang dengan K vokal berbeza

Dalam artikel ini, kita akan meneroka masalah mencari subrentetan terpanjang yang mengandungi vokal berbeza K dalam rentetan tertentu. Masalah ini boleh diselesaikan dalam C++ menggunakan algoritma yang berbeza. Masalah ini sering dihadapi dalam bidang sains komputer, terutamanya dalam pemprosesan teks dan tugas pemprosesan bahasa semula jadi. Ia mengkaji keupayaan seseorang untuk memanipulasi rentetan dan mengendalikan kes tepi.

Tatabahasa

Dalam medan C++, kelas std::string mewakili jenis data rentetan. Entiti serba boleh ini boleh digunakan untuk menyimpan dan memanipulasi jujukan aksara.

Kelas templat std::vector merangkumi ciri tatasusunan dinamik, membolehkan saiz tatasusunan dilaraskan dan satu siri operasi dilakukan pada elemen terkapsul.

Sebagai templat kelas, std::unordered_map merangkum struktur pemetaan tidak tertib. Ia membolehkan menyimpan satu pasangan nilai kunci tunggal di mana kunci kekal tidak sepadan dan nilai boleh diambil menggunakan kunci berbeza ini.

Templat fungsi std::max mengembalikan maksimum dua nilai. Mekanisme serba boleh ini memudahkan untuk membandingkan mana-mana jenis data, selagi pengendali >

std::string
std::vector
std::unordered_map
std::max

Algoritma

• Mula

• Mulakan pembolehubah untuk menyimpan subrentetan terpanjang dan panjangnya.

• Lelar melalui rentetan untuk mencari subrentetan dengan K vokal berbeza.

• Bandingkan panjang subrentetan dan kemas kini subrentetan terpanjang serta panjangnya dengan sewajarnya.

• Ulang langkah 2 dan 3 sehingga semua subrentetan telah dinilai.

• Kembalikan subrentetan terpanjang.

• Tamat

Kaedah

• Kaedah 1 - Brute Force

• Kaedah 2 − Tingkap gelongsor

Kaedah 1: Brute force cracking

Pelaksanaan ini merangkumi kaedah kekerasan untuk menemui subrentetan terpanjang rentetan dengan huruf vokal unik k. Kod ini bermula dengan mentakrifkan dua fungsi pembantu: is_vowel dan has_k_distinct_vowels.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Fungsi

is_vowel menerima satu aksara sebagai input dan mengembalikan nilai sebenar jika aksara itu ialah vokal (seperti 'a', 'e', ​​​​'i', 'o' atau 'u') dan nilai palsu sebaliknya. Fungsi ini kemudiannya digunakan untuk menentukan sama ada sesuatu aksara itu adalah vokal.

Fungsi

has_k_distinct_vowels menerima rentetan dan integer k sebagai input dan mengembalikan nilai sebenar jika rentetan mengandungi tepat k vokal unik, jika tidak ia mengembalikan nilai palsu. Fungsi ini menggunakan unordered_set untuk merekodkan vokal dalam rentetan dan mengira bilangan vokal unik dalam rentetan.

Fungsi utama longest_substring_bruteforce menerima rentetan dan integer k sebagai input dan mengembalikan subrentetan terpanjang dalam rentetan yang mengandungi betul-betul k vokal unik.

Ini dicapai dengan menggunakan dua gelung bersarang untuk mengulangi semua subrentetan rentetan yang mungkin. Untuk setiap subrentetan, ia memanggil fungsi has_k_distinct_vowels untuk mengesahkan sama ada subrentetan itu mempunyai betul-betul k vokal unik.

Jika subrentetan semasa mempunyai k vokal unik dan lebih lebar daripada subrentetan terpanjang semasa, subrentetan semasa akan menjadi subrentetan terpanjang baharu.

Akhir sekali, kod tersebut memasukkan rentetan dan integer k, memanggil fungsi longest_substring_bruteforce untuk mencari subrentetan terpanjang dengan vokal unik k, dan menghasilkan hasilnya.

#include <iostream>
#include <string>
#include <unordered_set>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

bool has_k_distinct_vowels(const std::string &s, int k) {
   std::unordered_set<char> vowel_set;
   for (char c : s) {
      if (is_vowel(c)) {
         vowel_set.insert(c);
      }
   }
   return vowel_set.size() == k;
}

std::string longest_substring_bruteforce(const std::string &s, int k) {
   std::string longest_substring = "";
   int max_len = 0;

   for (int i = 0; i < s.size(); ++i) {
      for (int j = i; j < s.size(); ++j) {
         std::string current_substring = s.substr(i, j - i + 1);
         if (has_k_distinct_vowels(current_substring, k) && current_substring.size() > max_len) {
         longest_substring = current_substring;
         max_len = current_substring.size();
         }
      }
   }

   return longest_substring;
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_bruteforce(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

Output

Longest substring with 3 distinct vowels: iaaioooaa

Kaedah 2: Tingkap gelongsor

Kaedah tetingkap gelongsor adalah teknik yang digunakan untuk menyelesaikan masalah sains komputer dan algoritma. Ia digunakan untuk mencari corak tertentu, seperti subrentetan atau subarray, yang memenuhi kriteria tertentu dalam input yang diberikan.

Dalam kaedah ini, dua penunjuk digunakan untuk mencipta tetingkap gelongsor yang meluncur mengikut input. Saiz tingkap dilaraskan mengikut keperluan untuk memastikan syarat yang diperlukan dipenuhi. Algoritma menjejaki sifat tetingkap semasa, seperti bilangan elemen berbeza, jumlah elemen, dsb.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Fungsi

is_vowel ialah fungsi pembantu yang mengembalikan benar jika aksara yang diberikan ialah vokal (iaitu a, e, i, o atau u).

Fungsi utama longest_substring_slidingwindow menerima rentetan s dan integer k sebagai input. Ia menggunakan dua penunjuk ke kiri dan kanan untuk mencipta tetingkap gelongsor dan mengulangi rentetan.

Gunakan kekerapan peta tidak tersusun untuk menjejaki kekerapan setiap vokal dalam tetingkap semasa. Apabila kekerapan vokal dalam tetingkap melebihi k, gerakkan penunjuk kiri ke kanan sehingga kekerapan vokal itu sama dengan k semula. Panjang tetingkap semasa dikira sebagai kanan - kiri + 1, dan jika ia lebih besar daripada panjang maksimum yang dilihat setakat ini, indeks dan panjang permulaan dikemas kini.

Akhir sekali, fungsi mengembalikan subrentetan terpanjang dengan k vokal berbeza menggunakan kaedah substr kelas String.

#include <iostream>
#include <string>
#include <unordered_map>

bool is_vowel(char c) {
   return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

std::string longest_substring_slidingwindow(const std::string &s, int k) {
   int left = 0, right = 0, max_len = 0, start = 0;
   std::unordered_map<char, int> freq;

   while (right < s.size()) {
      char c = s[right];
      if (is_vowel(c)) {
         freq[c]++;
      }

      while (freq.size() > k) {
         char left_char = s[left];
         if (is_vowel(left_char)) {
            freq[left_char]--;
            if (freq[left_char] == 0) {
               freq.erase(left_char);
            }
         }
         left++;
      }

      if (freq.size() == k && (right - left + 1) > max_len) {
         max_len = right - left + 1;
         start = left;
      }

      right++;
   }

   return s.substr(start, max_len);
}

int main() {
   std::string input = "aeiaaioooaauuaeiu";
   int k = 3;
   std::string result = longest_substring_slidingwindow(input, k);
   std::cout << "Longest substring with " << k << " distinct vowels: " << result << std::endl;
   return 0;
}

输出

Longest substring with 3 distinct vowels: iaaioooaa

结论

在本文中，我们讨论了两种方法来解决在给定字符串中找到包含K个不同元音字母的最长子串的问题。第一种方法是暴力法，而第二种方法是滑动窗口法。暴力法的时间复杂度为O(n^3)，使其成为更适合处理较大输入的解决方案。滑动窗口法由于其较低的时间复杂度，推荐用于解决这个问题。

Atas ialah kandungan terperinci Substring terpanjang dengan K vokal berbeza. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!