Menyemak sama ada subrentetan S1 berlaku selepas sebarang kejadian subrentetan S2 dalam ayat yang diberikan

Dalam masalah ini, kita perlu menyemak sama ada subrentetan S1 muncul selepas sebarang kejadian subrentetan S2 dalam rentetan S tertentu. Kita boleh menyelesaikan masalah ini dengan membandingkan indeks permulaan S1 dan S2 dalam rentetan S. p>

Pernyataan Masalah - Kami diberi tiga subrentetan bernama S, S1 dan S2. Rentetan S sentiasa mengandungi S1 sebagai subrentetan. Kita perlu menyemak sama ada subrentetan S1 muncul selepas subrentetan S2 dalam rentetan S yang diberikan.

Contoh

Masukkan – S = “abxtutorialspointwelcomepoint”, S1 = “Selamat Datang”, S2 = “Titik”

Output - Ya

Penjelasan – Dalam rentetan S, subrentetan "titik" muncul 2 kali. Satu sebelum "selamat datang" dan satu lagi selepas "selamat datang". Jadi, kita boleh katakan bahawa rentetan S1 berlaku selepas sebarang kejadian rentetan S2

Input– S = "abcdefgh", S1 = "abcd", S2 = "gh";

Output – Tidak

PenjelasanS1 adalah pada permulaan rentetan S. Oleh itu, S1 tidak akan muncul selepas subrentetan S2.

Masukkan – S = “abce”, S1 = “bc”, S2 = “xy”

Output – Tidak

Penjelasan – Oleh kerana rentetan S2 tidak wujud dalam rentetan S, cetak No.

Kaedah 1

Dalam kaedah ini kita akan menemui semua indeks permulaan subrentetan S2 dan menyimpannya dalam koleksi. Selepas itu, kita akan mendapat indeks permulaan S1. Kami membandingkan setiap indeks permulaan S2 dengan indeks permulaan S1 dan jika kami mendapati sebarang nilai dalam set kurang daripada indeks permulaan S2, maka kita boleh mengatakan bahawa subrentetan S1 berlaku selepas sebarang kejadian subrentetan S2 .

Algoritma

• Tentukan koleksi yang menyimpan indeks permulaan subrentetan S2.

• Gunakan kaedah find() untuk mencari indeks permulaan pertama subrentetan S2.

• Gunakan gelung sementara untuk mendapatkan semua indeks permulaan subrentetan S2 dan simpannya ke dalam koleksi menggunakan kaedah insert().

• Melintasi nilai yang ditetapkan. Mengembalikan benar jika sebarang nilai kurang daripada indeks permulaan subrentetan S1 dalam rentetan S yang diberikan.

• Akhirnya kembali palsu.

Contoh

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isS1AfterS2(string& S, string& S1, string& S2) {
   // set to store indices of S2 in S
   unordered_set<int> indices;
   // Find all occurrences of S2 in S, and store them in set
   size_t found = S.find(S2);
   while (found != string::npos) {
      indices.insert(found);
      found = S.find(S2, found + 1);
   }
   // Compare starting indices of S1 with S2
   for (const int& index : indices) {
      if (index < S.find(S1)) {
          return true;  // S2 appears before S1
      }
   }
   return false;  // S1 appears before or at the same position as S2
}
int main(){
   string S = "abxtutorialspointwelcomepoint";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
          cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}

Output

Yes, string S1 appears after string S2.

Kerumitan masa - O(N*K), kerana kita perlu mencari indeks permulaan rentetan S2.

Kerumitan ruang - O(N) kerana kami menyimpan indeks permulaan rentetan S2.

Kaedah 2

Dalam kaedah ini kita akan mengulangi rentetan. Mengembalikan benar jika kita mendapati bahawa S2 berlaku sebelum S1 kerana rentetan S sentiasa mengandungi rentetan S1.

Algoritma

• Takrifkan pembolehubah len, n1 dan n2 untuk menyimpan panjang pembolehubah.

• Mula melintasi tali.

• Tentukan 'rentetan temp dan mulakannya dengan subrentetan panjang n2 bermula pada indeks ke-i.

• Jika suhu == S2, kembalikan benar.

• Dapatkan subrentetan panjang n1 bermula dari indeks ke-i. Jika temp == s1, mengembalikan palsu.

• Akhirnya kembali benar.

Contoh

#include <bits/stdc++.h>
using namespace std;
bool isS1AfterS2(string &S, string &S1, string &S2){
   // store the length of the strings
   int n1 = S1.size(), n2 = S2.size();
   // Traverse the string S from left to right
   for (int i = 0; i <= S.size() - n2; i++){
      // temporary string to store substring
      string temp;
      // get the substring
      temp = S.substr(i, n2);
      // if we find the string S2, return true as s1 always present in s.
      if (temp == S2){
          return true;
      }
      temp = S.substr(i, n1);
      // If we find s1 before s2, return false
      if (temp == S1){
          return false;
      }
   }
   return true;
}
int main(){
   string S = "abxtutorialspointwelcome";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
      cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}

Output

Yes, string S1 appears after string S2.

Kerumitan masa – O(N*min(n1, n2)), kerana kita menemui subrentetan panjang n1 dan n2.

Kerumitan ruang - O(min(n1, n2) kerana kami menyimpan subrentetan.

Dalam kaedah pertama, kami menggunakan koleksi untuk menyimpan indeks permulaan S2, yang memerlukan lebih banyak ruang daripada kod kaedah kedua. Kod kaedah kedua lebih mudah dibaca daripada kaedah pertama. Sebagai alternatif, pengaturcara boleh cuba menyelesaikan masalah menyemak sama ada subrentetan S2 muncul selepas S1 muncul.

Atas ialah kandungan terperinci Menyemak sama ada subrentetan S1 berlaku selepas sebarang kejadian subrentetan S2 dalam ayat yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!