本文深入探讨了一个有趣的字符串操作问题：“使用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++代码：
#includeusing namespace std;vector constructZArray(string str) { int n = str.length(); vector Z(n, 0); int L = 0, R = 0; for (int i = 1; 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 Z = constructZArray(P); vector 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算法从给定的字符串中删除所有出现的单词的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444348.html
微信扫一扫 
支付宝扫一扫 
