5.3 子字符串查找
Robert Sedgewick Kevin Wayne
字符串的一种基本操作就是子字符串查找：给定一段长度为
的文本和一个长度为
的模式（pattern）字符串，在文本中找到一个和该模式相符的子字符串，请见图 5.3.1。解决该问题的大部分算法都可以很容易地扩展为找出文本中所有和该模式相符的子字符串、统计该模式在文本中的出现次数、或者找出上下文（和该模式相符的子字符串周围的文字）的算法。
的文本和一个长度为 的模式（pattern）字符串，在文本中找到一个和该模式相符的子字符串，请见图 5.3.1。解决该问题的大部分算法都可以很容易地扩展为找出文本中所有和该模式相符的子字符串、统计该模式在文本中的出现次数、或者找出上下文（和该模式相符的子字符串周围的文字）的算法。
图 5.3.1 子字符串的查找
当你在文本编辑器或是浏览器中查找某个单词时，就是在查找子字符串。事实上，该问题的原始动机就是为了支持这种查找操作。字符串查找的另一个经典应用是在截获的通信内容中寻找某种重要的模式。一位军队将领感兴趣的可能是在截获的文本中寻找和“拂晓进攻”类似的字句。一名黑客感兴趣的可能是在内存中查找与“Password:”相关的内容。在今天的世界中，我们经常在互联网的海量信息中查找字符串。
为了更好地理解算法，请记住模式相对于文本是很短的（ 可能等于 100 或者 1000），而文本相对于模式是很长的（ 可能等于 100 万或者 10 亿）。在字符串查找中，一般会对模式进行预处理来支持在文本中的快速查找。
可能等于 100 或者 1000），而文本相对于模式是很长的（ 可能等于 100 万或者 10 亿）。在字符串查找中，一般会对模式进行预处理来支持在文本中的快速查找。字符串查找是一个很有趣而且也很经典的问题：人们发明了几个截然不同（且令人惊讶的）算法，它们不仅产生了一系列能够实际应用的查找方法，而且也展示了许多重要的算法设计技巧。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了子字符串查找的基本操作，从暴力算法到更高效的Knuth-Morris-Pratt算法、Boyer-Moore算法以及Rabin-Karp算法。文章指出了暴力算法在最坏情况下的运行时间与文本长度N和模式长度M的乘积成正比，但在实际应用中，其运行时间一般与N+M成正比。强调了字符串查找在实际应用中的重要性，如在文本编辑器中查找单词、截获通信内容中寻找重要模式等。同时，也提到了算法设计的重要性和不断研究更好算法的必要性。总的来说，本文通过介绍子字符串查找的基本问题和经典算法，展示了算法设计的重要性和不断进步的可能性。读者可以从中了解到字符串查找问题的重要性以及不同算法的特点和应用场景。文章还详细介绍了Knuth-Morris-Pratt算法的原理和构造DFA的过程，通过图示和代码展示了算法的实现过程，使读者能够深入理解该算法的工作原理和实现细节。整体而言，本文内容丰富，适合对字符串查找算法感兴趣的读者阅读学习。文章还介绍了Rabin-Karp算法的实现细节和小技巧，展示了该算法的高效性和可靠性。通过对比各种算法的特点和性能，读者可以更好地理解不同算法的适用场景和优劣势。文章内容丰富，适合对字符串查找算法感兴趣的读者阅读学习。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论