strstr使用什么字符串搜索算法？

Question

我在读通过String searching algorithm维基百科文章，它让我想知道什么算法strstr在Visual Studio中使用？我应该尝试使用另一种实现方式，还是相当快速地使用strstr？

谢谢！

Answer 1

正如其他人所建议的：简介。执行有效的性能测试。

没有配置文件数据，您可能会优化部分运行20％的代码，浪费投资回报。

开发成本是现代计算机最关心的问题，而不是执行时间。最好的使用时间是在进入系统测试之前开发程序以正确运行并且出现少量错误。这是重点应该放在哪里。同样由于这个原因，只要功能正常工作，大多数人并不关心Visual Studio如何实现strstr。

请注意，有线或点的线性搜索优于其他搜索。该行取决于数据的大小或搜索条件。例如，使用具有分支预测的处理器和大指令高速缓存的线性搜索可能优于用于中小数据量的其他技术。更复杂的算法可能会有更多的分支导致指令缓存或数据缓存的重新加载（浪费执行时间）。

另一种优化程序的方法是使数据组织更容易搜索。例如，使字符串足够小以适应高速缓存行。这也取决于搜索的数量。对于大量搜索，优化数据结构可能会获得一些性能。

总之，优化当且仅当程序运行不正常，用户抱怨速度，缺少时序约束或不适合分配的内存。接下来的步骤是分析和优化大部分时间花费的区域。任何其他优化都是徒劳的。

Answer 2

C++标准是指用于描述什么是strstr的C标准。 C标准似乎没有对复杂性进行任何限制，所以几乎任何发现子字符串的第一个实例的算法都是合规的。

因此不同的实现可以选择不同的算法。你必须看看你的特定实现来确定它使用的是什么。

简单，蛮力方法可能O（米× n）其中米和Ñ是串的长度。如果你需要比这更好，你可以尝试其他库，比如Boost，或者自己实现一个子线性搜索。

Answer 3

在visual studio strstr中的实现不知道给我，我不确定它是否对任何人。但是，我发现这些有趣的sources和example实施。后者显示该算法在最坏情况下以所搜索字符串的大小二次运行。总计应该少于这个数字。非随机解的算法极限应该是这样的。

实际情况是，根据输入的大小，可能会使用不同的算法，主要针对金属进行优化。然而，人们无法真正打赌。如果你正在做DNA测序，strstr和家庭是非常重要的，很可能你将不得不编写自己的定制版本。通常，标准实现针对一般情况进行了优化，但另一方面，在编译器上工作的人知道他们的员工。无论如何，你不应该把自己的技能打赌给专业人士。

但是，所有关于开发时间的讨论都会伤害编写优秀软件的努力。在开始这项工作之前，确保重写一个自定义strstr的好处超过了维护和调整你的特定情况所需的努力。