Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
用KMP
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 |
class
Solution {public: char
*strStr(char
*haystack, char
*needle) { int
size = 0; for(;haystack[size]!=‘\0‘
;size++); int
size_needle =0; while(needle[size_needle]!=‘\0‘)size_needle++; if(size_needle == 0 )return
haystack; vector<int> patten(size_needle,0); generatepatten(needle,size_needle,patten); int
i = 0; int
ind = 0; while( i < size ) { if(haystack[i] == needle[ind] ) { i++; ind++; if(ind == size_needle ) return
haystack + i - size_needle; } else { i = i - ind + patten[ind] +1; ind = 0; } } return
NULL; } void
generatepatten(char
* needle , int
size , vector<int> & patten) { int
len = 0; for(int
i = 1 ; i < size ;i++) { if(needle[i] == needle[len]) { patten[i] = ++len; } else { patten[i] = 0; len = 0; } } }}; |
Implement strStr(),布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3615654.html