首页 >后端开发 >C++ >使用Z算法从给定的字符串中删除所有出现的单词

使用Z算法从给定的字符串中删除所有出现的单词

WBOY
WBOY转载
2023-09-03 23:13:06759浏览

使用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中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除