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.
解法1：暴力破解法，两重循环进行搜索，时间复杂度O(mn)。
class Solution { public: int strStr(string haystack, string needle) { int n = haystack.size(), m = needle.size(); if(n == 0 || m == 0) { if(n >= 0 && m == 0) return 0; return -1; } for(int i = 0; i < n - m + 1; i++) { int j = 0; for(; j < m; j++) { if(haystack[i + j] != needle[j]) break; } if(j == m) return i; } return -1; } };
解法2：在haystack里面匹配needle，使用Sunday算法进行模式匹配。时间复杂度O(m+n)。
class Solution { public: int strStr(string haystack, string needle) { int pos = -1; bool res = sunday(haystack, needle, pos); return pos; } private: bool sunday(const string& text, const string& patt, int& pos) { int ts = text.size(); int ps = patt.size(); if (ts <= 0 || ps <= 0) { if (ts >= 0 && ps == 0) { pos = 0; return true; } return false; } vector<int> dis_tab(256, ps + 1); for (int i = 0; i < ps; ++i) dis_tab[(unsigned int)patt[i]] = ps - i; int end = ts - ps + 1; for (int i = 0; i < end;) { int j = 0; if (text[i] == patt[0]) while (i < ts && j < ps && text[i + j] == patt[j]) ++j; if (j == ps) { pos = i + j - ps; return true; } i += dis_tab[text[i + ps]]; } return false; } };
[LeetCode]44. Implement strStr()实现strStr()函数
原文：http://www.cnblogs.com/aprilcheny/p/4912395.html