[LeetCode]28.Implement strStr()

【题目】

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

【题意】

实现strStr（）功能。

【分析】

暴力算法代码如下。更高效的的算法有 KMP 算法、Boyer-Mooer 算法和Rabin-Karp 算法。面试中暴力算法足够了。

具体参考：KMP字符串模式匹配详解

【代码】

/*********************************
*   日期：2014-02-02
*   作者：SJF0115
*   题号: Implement strStr()
*   来源：http://oj.leetcode.com/problems/implement-strstr/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

class Solution {
public:
    char* strStr(char *haystack, char *needle) {
        if(needle == NULL || haystack == NULL){
            return NULL;
        }
        int offset;
        int m = strlen(haystack);
        int n = strlen(needle);
        for(int i = 0;i < m - n + 1;i++){
            for(offset = 0;offset < n;){
                if(haystack[i+offset] == needle[offset]){
                    offset++;
                }
                else{
                    break;
                }
            }
            if(offset == n){
                return haystack+i;
            }
        }
        return NULL;
    }
};

int main() {
    Solution solution;
    char *haystack = "abcedf";
    char *needle = "edf";
    char *str = solution.strStr(haystack,needle);
    cout<<str<<endl;
    return 0;
}