实现 strStr() 函数。
    给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
    当 needle 是空字符串时，返回 0

    示例 1：
    输入：haystack = “hello”, needle = “ll”
    输出：2

    示例 2：
    输入：haystack = “aaaaa”, needle = “bba”
    输出：-1

    1. public int strStr(String haystack, String needle) {
    2.     // needle 空字符串，返回 0 
    3.     if ("".equals(needle)) {
    4.         return 0;
    5.     }
    6.     // needle 比 haystack 长，必定不存在
    7.     if (needle.length() > haystack.length()) {
    8.         return -1;
    9.     }
    11.     for(int i = 0; i < haystack.length(); i++) {
    12.         // 依次比较字符
    13.         char c = haystack.charAt(i);
    14.         if (needle.charAt(0) == c) {
    15.             // 若遇到字符相同，比较 haystack 剩余长度是否足够，若不足，则必然不存在
    16.             if ((i + needle.length()) > haystack.length()) {
    17.                 break;
    18.             }
    19.             // 截取 haystack 剩余部分字符串，并且和 needle 比较，若相等，则 i 即出现的第一个位置
    20.             String subHaystack = haystack.substring(i, i + needle.length());
    21.             if (subHaystack.equals(needle)) {
    22.                 return i;
    23.             }
    24.         }
    25.     }
    26.     return -1;
    27. }

    其实后半部分即字符串匹配问题，可以利用 BF 算法进行字符串匹配：

    1. public int strStr(String haystack, String needle) {
    2.     // needle 空字符串，返回 0
    3.     if ("".equals(needle)) {
    4.         return 0;
    5.     }
    6.     // needle 比 haystack 长，必定不存在
    7.     if (needle.length() > haystack.length()) {
    8.         return -1;
    9.     }
    11.     return bfMatch(haystack, needle, 0);
    12. }
    14. public int bfMatch(String str, String sub, int pos) {
    15.     if (pos < 0 || pos > str.length()) {
    16.         return -1;
    17.     }
    18.     int baseIndex = pos;
    19.     int index = 0;
    20.     while(baseIndex < str.length() && index < sub.length()) {
    21.         if (str.charAt(baseIndex) == sub.charAt(index)) {
    22.             // 字符匹配
    23.             baseIndex++;
    24.             index++;
    25.         } else {
    26.             // 主串回退从新开始匹配
    27.             baseIndex = baseIndex - index + 1;
    28.             index = 0;
    29.         }
    30.     }
    32.     if (index >= sub.length()) {
    33.         // 子串匹配结束，计算匹配的起始位置
    34.         return baseIndex - index;
    35.     }
    37.     return -1;
    38. }

    而字符串匹配 BF 算法可以优化为 RF 算法，KMP 算法等等