Implement strStr().
 Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
 Example 1:
 Input: haystack = "hello", needle = "ll"
 Output: 2
 Example 2:

Input: haystack = "aaaaa", needle = "bba"
 Output: -1 

int strStr(char* haystack, char* needle) 
{
    int hlen = strlen(haystack);
    int nlen = strlen(needle);
    
    if(nlen==0)
        return 0;
    
    if(hlen < nlen)
        return -1;

    for(int i = 0;i < hlen;i++)
    {
        int j = i;
        int k = 0;
        
        while(haystack[j] == needle[k] && k < nlen)
        {
            j += 1;
            k += 1;
        }
        
        if(k == nlen)
            return i;
    }
    
    return -1;
    
}

经验与教训

如果needle为空，应返回-1还是0呢？我们可以通过如下代码来验证。 

#include <stdio.h>
#include <string.h>

int main ()
{
  char str[] ="This is a simple string";
  char * pch;
  pch = strstr (str,"");
  printf("%c\n",*pch);
  return 0;
}

执行上述程序输出T，因此该练习中如果nlen为0,则return 0.
 提交之后，我们可以看到运行的时间及排名。
可以看到我们算法的运行效率仅击败了19.53%的人，因此使用下面更高效的算法 KMP算法。

当然下面的算法不是KMP算法，参考上面的链接可以知道KMP算法需要首先计算部分匹配表，用于如下情形，比如要在ABCDEFGHIJK中查找是否存在ABCDG，比较到最后时G不等于E，因此要从字符串ABCDEFGHIJK中的B开始比较，由于我们前面的比较可知，此时可以从F开始比较，KMP算法节省了比较次数。下面的算法属于偷懒版本的KMP，通过比较第一个字符是否相等进而判断是否比较. 

int strStr(char* haystack, char* needle) 
{
    int lh = strlen(haystack);
    int ln = strlen(needle);
    
    if((lh == 0 && ln == 0) || ln == 0 || needle == haystack)
      return 0;
    
    for (int i = 0; i <=(lh-ln); i++) 
    {
        if(haystack[i] == needle[0])
        {
            if(strncmp(haystack + i, needle, ln) == 0)
            {
                return i;
            }
        }
    }
    
    return -1;
}