c# - 手动实现 string.IndexOf

Question

我需要在不使用任何与 c# 字符串搜索相关的内置方法的情况下实现 string.IndexOf 功能。

您能否为此建议一个简单的算法。搜索不涉及非常大的字符串。您可以假设要搜索的字符串的最大长度为 1000 个字符。

Answer 1

由于这听起来像家庭作业，我将提供指导而不是解决方案。维基百科上对字符串搜索算法有一个很好的概述：

http://en.wikipedia.org/wiki/String_searching_algorithm

尝试实现 Naïve 字符串搜索作为对该主题的一个很好的介绍。

查看一个字符串在另一个字符串中出现位置的最简单且效率最低的方法是逐个检查它可能在的每个位置，看它是否在那里。所以首先我们看看大海捞针的第一个字符中是否有针的副本；如果没有，我们看看是否有从大海捞针的第二个字符开始的针的副本；如果不是，我们从第三个字符开始，以此类推。在正常情况下，我们只需要对每个错误的位置看一两个字符就可以看出它是一个错误的位置，所以在平均情况下，这需要 O(n + m) 步，其中 n 是干草堆，m是针的长度；但在最坏的情况下，在像“aaaaaaaaab”这样的字符串中搜索像“aaaab”这样的字符串需要 O(nm) 步。

Answer 2

您是否尝试过查看其他语言的实现。例如Java？

这些源代码广泛可用，向专家学习始终是良好的第一步。

Answer 3

另一个很好的指导是考虑“我可以避免一些搜索吗？” 例如，如果您的搜索字符串是aaaa并且搜索的字符串是aaabaaaabaaa并且您从位置 [0] 开始，您还需要在位置 [1] 进行搜索吗？

另外，搜索字符串中最适合开始匹配的字符是哪个？如果您的搜索字符串是abcd并且您搜索的字符串是aababceabcd，这是否暗示了您的匹配循环可能如何构建的某些方面？