问题

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3895 访问。

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

输入: haystack = "hello", needle = "ll"

输出: 2

输入: haystack = "aaaaa", needle = "bba"

输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

---

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Input: haystack = "hello", needle = "ll"

Output: 2

Input: haystack = "aaaaa", needle = "bba"

Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

---

示例

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3895 访问。

public class Program {

    public static void Main(string[] args) {
        var haystack = "hello";
        var needle = "ll";

        var res = StrStr(haystack, needle);
        Console.WriteLine(res);

        haystack = "mississippi";
        needle = "issipi";

        res = StrStr2(haystack, needle);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static int StrStr(string haystack, string needle) {
        //利用运行库，无耻的解法
        return haystack.IndexOf(needle);
    }

    private static int StrStr2(string haystack, string needle) {
        //定义匹配变量
        var match = true;
        //从首字母循环，后面的部分无需放在外循环
        //因为内循环可以比较到
        for(var i = 0; i <= haystack.Length - needle.Length; i++) {
            //默认为匹配
            match = true;
            for(var j = 0; j < needle.Length; j++) {
                //使用内循环逐一判定是否每个字母都能匹配
                if(haystack[i + j] != needle[j]) {
                    //发现不匹配时立刻退出内循环
                    match = false;
                    break;
                }
            }
            //如果全部匹配，则直接返回i
            if(match) return i;
        }
        //无法完成匹配
        return -1;
    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3895 访问。

2
-1

---

分析：

假设2个单词的长度分别为 m 和 n，那么显而易见，StrStr 的时间复杂度基于运行库的实现，StrStr2 的时间复杂度为：  。