Rumah  >  Artikel  >  pembangunan bahagian belakang  >  Menyemak sama ada rentetan boleh dibuat lebih kecil secara leksikografi dengan membalikkan sebarang subrentetan

Menyemak sama ada rentetan boleh dibuat lebih kecil secara leksikografi dengan membalikkan sebarang subrentetan

WBOY
WBOYke hadapan
2023-08-29 22:21:121074semak imbas

Menyemak sama ada rentetan boleh dibuat lebih kecil secara leksikografi dengan membalikkan sebarang subrentetan

Dalam C++, kami mempunyai fungsi reverse() terbina dalam untuk menterbalikkan subrentetan untuk memeriksa sama ada rentetan boleh menjadi lebih kecil dari segi leksikografi. Susunan kamus ialah proses menyusun aksara sesuatu perkataan ke dalam susunan kamus.

Mari kita ambil contoh rentetan untuk menyemak sama ada susunan leksikografik lebih kecil.

  • Kami akan membandingkan dua perkataan untuk menyemak perkataan yang lebih kecil dari segi leksikografi dan mengambil dua rentetan, iaitu 'apple' dan 'army'. Huruf pertama kedua-dua rentetan bermula dengan huruf ‘a’. Apabila kita meneliti watak kedua bagi dua huruf, mengikut abjad, ‘p’ didahulukan sebelum ‘r’. Oleh itu, dari segi leksikografi, epal adalah lebih kecil daripada tentera.

  • Dalam rentetan "tutorialspoint", membalikkan subrentetan "oria" memberikan "airo", yang lebih kecil dari segi leksikografi. Kemudian tulis rentetan akhir sebagai "tutairolspoint".

  • Dalam rentetan "tutorix", terbalikkan subrentetan "tori" untuk mendapatkan "irot", kerana watak permulaan subrentetan pertama ialah 't', dan yang kedua Substring ialah ' i', jadi 'i' didahulukan sebelum 't' dalam abjad, jadi 'irot' secara leksikografi lebih kecil daripada 'tori'. Penulisan rentetan akhir "tuirotx"

Kami akan mengambil contoh rentetan lain, seperti "acwz".

Tatabahasa

reverse( str_name.begin(), str_name.end() )

Arahan

Fungsi terbalik ialah sebahagian daripada pustaka standard C++ Ia menerima dua parameter "str_name.begin()" dan "str_name.end()".

  • str_name ialah nama rentetan yang dicadangkan pengguna.

  • begin() dan end() ialah fungsi terbina dalam yang dipratentukan yang digunakan di bawah fungsi songsang. Tugas fungsi mula adalah untuk mengembalikan iterator yang menunjuk ke aksara pertama rentetan input. Fungsi akhir mengembalikan iterator yang menunjuk ke kedudukan sebelum aksara terakhir rentetan input.

Sila ambil perhatian bahawa fungsi terbalik tidak mengembalikan apa-apa kerana ia secara langsung mengubah suai bekas (str_name).

Algoritma

  • Pertama, kami akan menggunakan tiga fail pengepala yang diperlukan, iaitu iostream, rentetan dan sertakan

  • Kita akan mulakan dengan fungsi utama di mana kita mengisytiharkan pembolehubah rentetan yang dipanggil ‘str’ dan menyimpan rentetan ‘tutorialspoint’ di dalamnya. Kami kemudiannya akan mengisytiharkan pembolehubah boolean ‘isReverse’ sebagai ‘false’ untuk menunjukkan bahawa rentetan yang diberikan belum diterbalikkan dan masih dalam bentuk asalnya.

  • Kami kemudiannya akan mencipta dua gelung bersarang untuk menyemak setiap subrentetan yang mungkin bagi ‘str’. Subrentetan itu kemudiannya disimpan dalam rentetan sementara bernama ‘temp’.

  • Selepas itu, kami memanggil fungsi 'reverse()' untuk membalikkan subrentetan 'j' yang disimpan dalam pembolehubah 'temp' antara indeks 'i' dan .

  • Kemudian buat pernyataan if untuk menyemak sama ada rentetan terbalik secara leksikografi kurang daripada pembolehubah ‘temp’ dan ‘str’ untuk perbandingan.

  • Pengkompil akan membandingkan pembolehubah temp dan str. Jika kedua-duanya adalah sama, maka pembolehubah ‘isReverse’ akan ditetapkan kepada benar dan ia akan memecahkan pernyataan if.

  • Sekarang, kami menyemak nilai isReverse dan jika ia benar, cetak pernyataan bersyarat if, jika tidak, cetak pernyataan bersyarat else.

  • Keluar dari program.

Contoh

Dalam program ini kita akan belajar cara membuat rentetan secara leksikografi lebih kecil dengan membalikkan mana-mana subrentetan.

#include <iostream>
#include <string>
#include <algorithm> 
using namespace std;
int main() {
   string str = "tutorialspoint";
   // User can change this to test other strings such as acwz, groffer, etc
   bool isReverse = false; // it is used to indicate whether or not a substring has been found in the original string “str”.


   // use the loop through all possible substrings of str
   for (int i = 0; i < str.length(); i++) {
      for (int j = i+1; j < str.length(); j++) {
         string temp = str; 
         // create new temporary variable to store the value of str.
         // reverse the substring of i and j
         reverse ( temp.begin() + i, temp.begin() + j + 1 ); 
         // reverse function follow the header file name as <algorithm>
         if (temp < str) { 
            // Check whether the reversed string is lexicographically smaller
            isReverse = true;
            break;
         }
      }
   }
   if ( isReverse ) {
      cout << "Yes, this is lexicographically smaller by reversing a  substring." << endl;
   } else {
      cout << "No, this is not lexicographically smaller by reversing a substring." << endl;
   }
   return 0;
}

Output

Jika kita masukkan nilai "tutorialspoint" kita akan dapat hasil seperti berikut -

Yes, this is lexicographically smaller by reversing a  substring.

Jika kita masukkan nilai "acwz" kita dapat hasil seperti berikut:

No, this is not lexicographically smaller by reversing a substring.

Kesimpulan

Kami melihat cara menggunakan pembolehubah rentetan untuk mengira nilai yang lebih kecil dalam kamus dengan membalikkan sebarang subrentetan. Kemudian kami menetapkan pembolehubah rentetan kepada pembolehubah sementara. Kami kemudian menggunakan fungsi yang telah ditetapkan "reverse()" untuk mengira perkataan kamus dalam bentuk songsangnya. Seterusnya, kami menyemak untuk leksikografi yang lebih kecil dengan membandingkan pembolehubah temp dan str dan mendapatkan hasilnya.

Atas ialah kandungan terperinci Menyemak sama ada rentetan boleh dibuat lebih kecil secara leksikografi dengan membalikkan sebarang subrentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Artikel ini dikembalikan pada:tutorialspoint.com. Jika ada pelanggaran, sila hubungi admin@php.cn Padam