使用Z演算法從給定的字串中刪除所有出現的單字

本文深入探討了一個有趣的字串操作問題：「使用Z演算法從給定字串中刪除所有出現的單字」。這個問題是Z演算法在模式搜尋問題中的一個很好的應用案例，突顯了它的有效性。讓我們詳細探討一下。

問題陳述

給定一個字串S和一個單字W，任務是使用Z演算法從S中刪除所有W的出現。

理解問題

考慮一個字串 S =「HelloWorldHelloWorld」和一個單字 W =「World」。目標是從 S 中刪除所有出現的 W。因此，輸出將為“HelloHello”。

Z-演算法

Z演算法可以在線性時間內找到文字中模式的所有出現。它建立了一個陣列（Z數組），其中對於給定的索引i，Z[i]表示從i開始的最長子字串的長度，該子字串也是字串的前綴。

演算法方法

以下是解決問題的步驟 -

• 建立一個新的字串 P = W '$' S。

• 將 Z 演算法應用於 P 並建構 Z 陣列。

• 迭代 Z 陣列。如果 Z[i] 等於 W 的長度，則表示 W 存在於該索引處。在該索引處從 S 中刪除 W。

Example

的中文翻譯為：

範例

這是一個實作上述方法的C 程式碼：

#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;
}

輸出

String after removal: Iam

測試案例範例

讓我們考慮一個例子 -

假設 S = "Iamwritingwriting"，W = "writing"。程式將輸出 "Iam"。原因如下 −

• 新的字串P變成"writing$Iamwritingwriting"。

• 應用Z演算法後，我們發現Z[8]和Z[15]等於W的長度，這意味著W存在於S中的這些索引處。

  李>

• 然後我們從S移除這些索引中的W，得到字串"Iam"。

結論

Z 演算法是解決模式搜尋問題的強大工具。在本文中，我們看到了它在從字串中刪除所有出現的單字方面的應用。這個問題是一個很好的例子，展示了理解和應用字串匹配演算法的好處。永遠記住，理解和學習演算法開啟了解決複雜問題的方法。

以上是使用Z演算法從給定的字串中刪除所有出現的單字的詳細內容。更多資訊請關注PHP中文網其他相關文章！