对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。

在线评测地址：
https://www.lintcode.com/problem/implement-strstr/?utm_source=sc-tianchi-sz0825

说明

在面试中我是否需要实现KMP算法？

不需要，当这种问题出现在面试中时，面试官很可能只是想要测试一下你的基础应用能力。当然你需要先跟面试官确认清楚要怎么实现这个题。
《九章算法班》：https://www.jiuzhang.com/course/71/?utm_source=sc-tianchi-sz0825
中讲过比KMP更简单的算法：Rabin-karp 算法，可免费试听。
样例 1:

输入: source = "source" ， target = "target"
输出:-1
样例解释: 如果source里没有包含target的内容，返回-1
样例 2:

输入: source = "abcdabcdefg" ，target = "bcd"
输出: 1
样例解释: 如果source里包含target的内容，返回target在source里第一次出现的位置
【题解】

算法：模拟

算法思路

因为本题的时间复杂度比较宽限，不需要更为复杂的KMP算法，可以直接模拟，逐一比对每个字符。

代码思路

先进行特判，若target长度为0，则返回0；若target的长度大于source，则表示不可能匹配，返回-1
枚举匹配source的起始位置，从0到sourceLen-targetLen
对于一个起始位置，比对之后的targetLen位是否相同，若遇到不相同直接退出判断，尝试下一个起始位置
当成功比对完targetLen位后，说明全部相同，则返回起始位置
复杂度分析

M表示 source 的长度

N表示 target 的长度

空间复杂度：O(M+N)

时间复杂度：O(MN)

public class Solution {

/**
 * @param source: 
 * @param target: 
 * @return: return the index
 */

public int strStr(String source, String target) {

    //获取两个字符串的长度
    int sourceLen = source.length();
    int targetLen = target.length();

    //注意特判，若target长度为0则答案为0
    if(targetLen == 0){
        return 0;
    }

    //若target长度大于source，则不可能匹配
    if(targetLen > sourceLen){
        return -1;
    }

    for(int i = 0; i < sourceLen-targetLen+1; i++){
        //k表示比对时source中所指向的字符
        int k = i;
        for(int j = 0; j < targetLen; j++){
            if(source.charAt(k) == target.charAt(j)){
                //最后一个字符匹配完成，输出答案
                if(j == targetLen - 1){
                    return i;
                }
                k++;
            }
            //其中一个字符无法匹配，直接退出做下一次循环
            else{
                break;
            }
        }
    }
    return -1;

更多题解参见九章算法官网：
https://www.jiuzhang.com/solution/implement-strstr/?utm_source=sc-tianchi-sz0825)