题目链接:Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button to reset your code definition.
这道题的要求是实现strStr()函数,返回needle在haystack中第一次出现的位置,如果没找到,这返回-1。
这道题的直接思路就是暴力查找,就是一个字符一个字符地进行匹配。不多说了,如果有兴趣,可以去研究这几个O(m+n)的算法:Rabin-Karp算法、KMP算法和Boyer-Moore算法。
时间复杂度:O(mn)
空间复杂度:O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
int strStr(char *haystack, char *needle)
{
int l1 = strlen(haystack), l2 = strlen(needle);
for(int i = 0, j; i <= l1 - l2; ++ i)
{
for(j = 0; j < l2 && haystack[i + j] == needle[j]; ++ j);
if(j == l2)
return i;
}
return -1;
}
};