Alih keluar semua kemunculan perkataan daripada rentetan yang diberikan menggunakan algoritma Z

Artikel ini menyelidiki masalah manipulasi rentetan yang menarik: "Alih keluar semua kemunculan perkataan daripada rentetan yang diberikan menggunakan algoritma Z". Masalah ini ialah kes aplikasi yang baik bagi algoritma Z dalam masalah carian corak, menonjolkan keberkesanannya. Mari kita terokai ini secara terperinci.

Pernyataan Masalah

Diberi rentetan S dan perkataan W, tugasnya adalah untuk mengalih keluar semua kejadian W daripada S menggunakan algoritma Z.

Pemahaman Soalan

Pertimbangkan rentetan S = "HelloWorldHelloWorld" dan perkataan W = "World". Matlamatnya adalah untuk mengalih keluar semua kejadian W daripada S. Oleh itu, output akan menjadi "HelloHello".

Z-Algoritma

Algoritma Z boleh mencari semua kejadian corak dalam teks dalam masa linear. Ia membina tatasusunan (tatasusunan Z) di mana untuk indeks i tertentu, Z[i] mewakili panjang subrentetan terpanjang bermula dari i, yang juga merupakan awalan rentetan.

Kaedah Algoritma

Berikut adalah langkah-langkah untuk menyelesaikan masalah -

• Buat rentetan baharu P = W + '$' + S.

• Gunakan algoritma Z pada P dan bina tatasusunan Z.

• Lelaran pada tatasusunan Z. Jika Z[i] sama dengan panjang W, bermakna W wujud pada indeks tersebut. Alih keluar W daripada S pada indeks itu.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Ini ialah kod C++ yang melaksanakan kaedah di atas:

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

vector<int> constructZArray(string str) {
   int n = str.length();
   vector<int> Z(n, 0);
   int L = 0, R = 0;
   for (int i = 1; i < n; i++) {
      if (i > R) {
         L = R = i;
         while (R < n && str[R - L] == str[R])
               R++;
         Z[i] = R - L;
         R--;
      } else {
         int k = i - L;
         if (Z[k] < R - i + 1)
               Z[i] = Z[k];
         else {
               L = i;
               while (R < n && str[R - L] == str[R])
                  R++;
               Z[i] = R - L;
               R--;
         }
      }
   }
   return Z;
}

string removeWord(string S, string W) {
   string P = W + '$' + S;
   int len_W = W.length();
   vector<int> Z = constructZArray(P);
   vector<bool> toRemove(S.size(), false);
   for (int i = len_W + 1; i < Z.size(); i++) {
      if (Z[i] == len_W)
         fill(toRemove.begin() + i - len_W - 1, toRemove.begin() + i - 1, true);
   }
   
   string result = "";
   for (int i = 0; i < S.size(); i++) {
      if (!toRemove[i])
         result += S[i];
   }
   return result;
}

int main() {
   string S, W;
   S="Iamwritingwriting";
   W = "writing";
   cout << "String after removal: " << removeWord(S, W);
   return 0;
}

Output

String after removal: Iam

Contoh kes ujian

Mari kita pertimbangkan contoh -

Andaikan S = "Iamwritingwriting", W = "writing". Program ini akan mencetak "Iam". Sebabnya adalah seperti berikut −

• Rentetan baru P menjadi "menulis$Iamwritingwriting".

• Selepas menggunakan algoritma Z, kami mendapati bahawa Z[8] dan Z[15] adalah sama dengan panjang W, yang bermaksud bahawa W wujud pada indeks ini dalam S.

  李>

• Kemudian kita keluarkan W dalam indeks ini daripada S untuk mendapatkan rentetan "Iam".

KESIMPULAN

Algoritma

Z ialah alat yang berkuasa untuk menyelesaikan masalah carian corak. Dalam artikel ini, kami melihat penggunaannya dalam mengalih keluar semua kemunculan perkataan daripada rentetan. Soalan ini ialah contoh yang bagus tentang faedah memahami dan menggunakan algoritma padanan rentetan. Sentiasa ingat bahawa pemahaman dan pembelajaran algoritma membuka cara untuk menyelesaikan masalah yang kompleks.

Atas ialah kandungan terperinci Alih keluar semua kemunculan perkataan daripada rentetan yang diberikan menggunakan algoritma Z. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!