248
技術社區[雲棲]
[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()
* 來源：https://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;
}
最後更新：2017-04-03 12:54:57