Description
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Discussion
判断needle是否是haystack的子串，并返回子串的起始位置。
暴力破解法。每次判断haystack串的i～i+m子串是否与needle相等。
算法的时间复杂度为O(nm)。
Rabin-Karp字符串查找算法。一种非常经典的算法。每次从haystack中取出长度为m的子串，然后将该子串进行哈希，并将其哈希值与needle串的哈希值进行比较。若哈希值相等再把相关字符一一比较。
算法的时间复杂度为O(mn)，实际使用中一般认为是O(n + m)。
Rolling Hash。https://en.wikipedia.org/wiki/Rolling_hash
算法的时间复杂度为O(n)。
C++ Code
仅给出暴力破解代码。
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.length();
int m = needle.length();
if(n < m)
{
return -1;
}
for(int i = 0; i < n - m + 1; i++)
{
int isStr = 1; //判断i～i+m是否与haystack相等。
for(int j = 0; j < m; j++)
{
if(haystack[i + j] != needle[j])
{
isStr = 0;
break;
}
}
if(isStr)
{
return i;
}
}
return -1;
}
};