Posted on 2014-01-11 02:20
Uriel 阅读(104)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
实现strstr函数，直接上KMP模板了...
trick是模板串为空的情况，此时直接返回待查串头指针
1 class Solution {
2 public:
3 int nxt[1000010];
4 void GetNxt(char *str) {
5 nxt[0] = -1;
6 int i = 1, j = 0;
7 while(str[i]) {
8 if(j == -1 || str[i] == str[j]) {
9 ++i; ++j;
10 if(str[i] != str[j]) nxt[i] = j;
11 else
12 nxt[i] = nxt[j];
13 }
14 else
15 j = nxt[j];
16 }
17 }
18
19 char *strStr(char *haystack, char *needle) {
20 int i = 0, j = 0, s_len, p_len, sum = 0;
21 GetNxt(needle);
22 s_len = strlen(haystack); p_len = strlen(needle);
23 if(p_len == 0) return haystack;
24 M: while(i < s_len && j < p_len) {
25 if(j == -1 || haystack[i] == needle[j]) {
26 if(j == p_len - 1) return haystack + i - p_len + 1;
27 ++i; ++j;
28 }
29 else
30 j = nxt[j];
31 }
32 return NULL;
33 }
34 };