10.实现strStr

题号28：

实现strStr()。

返回蕴含在 haystack 中的 needle 的第一个字符的索引，如果 needle 不是 haystack 的一部分则返回-1 。

例 1:

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

输出:2

例 2:

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

输出:-1

解题思路：

模式匹配。用了最简单粗暴的办法，之前学过KMP及其改进算法，但暂时写不出对应程序，二刷的时候再贴改进版。

遍历给定字符串haystack，当某个字符haystack[i]与needle[0]相同时，遍历needle，判断needle是否是haystack的一部分；

若needle[j]与haystack[i+j]有一个字符不匹配，则跳出needle的遍历，继续向前遍历haystack；

若needle[j]与haystack[i+j]都匹配（即needle中的字符已全部遍历，此时j==needle的长度），则返回当前的位置i。

代码实现：

class Solution {

public:

int strStr(string haystack, string needle) {

if(needle.length()==0) return 0;

for(int i=0;i

if(haystack[i]==needle[0]){

int j=0;

for(;j

if(haystack[i+j]!=needle[j]){

break;

}

}

if(j==needle.length()){

return i;

}

}

}

return -1;

}

};