forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstrStr.cpp
More file actions
122 lines (103 loc) · 2.74 KB
/
Copy pathstrStr.cpp
File metadata and controls
122 lines (103 loc) · 2.74 KB
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// Source : https://oj.leetcode.com/problems/implement-strstr/
// Author : Hao Chen
// Date : 2014-07-19
/**********************************************************************************
*
* Implement strStr().
*
* Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
*
*
**********************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
char *strStr1(char *haystack, char *needle);
char *strStr2(char *haystack, char *needle);
char *strStr(char*haystack, char *needle) {
if (random()%2){
printf("---KMP---\n");
return strStr1(haystack, needle);
}
printf("---brute-force---\n");
return strStr2(haystack, needle);
}
//KMP
char *strStr1(char *haystack, char *needle) {
if(!haystack || !needle ) {
return NULL;
}
if (!*needle ) {
return haystack;
}
char *ph = haystack;
char *pn = needle;
for( ;*ph && *pn ; ph++, pn++ );
//len(haystack) < len(needle)
if (!*ph && *pn){
return NULL;
}
for(ph=ph-1; *ph; haystack++, ph++) {
char *q=needle;
char *p=haystack;
int n=0;
while(*q && *p && *p==*q){
p++; q++;
if (n==0 && *p == *needle){
n = p - haystack;
}
}
if (!*q){
return haystack;
}
haystack += (n>0 ? n-1 : n);
}
return NULL;
}
//brute-force
char *strStr2(char *haystack, char *needle) {
if(!haystack || !needle ) {
return NULL;
}
if (!*needle ) {
return haystack;
}
char *ph = haystack;
char* pn = needle;
for( ;*ph && *pn ; ph++, pn++ );
//len(haystack) < len(needle)
if (!*ph && *pn){
return NULL;
}
ph--;
for( ; *ph; haystack++, ph++) {
char *q=needle;
char *p=haystack;
while(*q && *p && *p==*q){
p++; q++;
}
if (!*q){
return haystack;
}
}
return NULL;
}
int main(int argc, char** argv)
{
srand(time(0));
const char* haystack = "mississippi";
const char* needle = "issi";
printf("%s, %s : %s\n", haystack, needle, strStr((char*)haystack, (char*)needle));
haystack = "mississippi";
needle = "issip";
printf("%s, %s : %s\n", haystack, needle, strStr((char*)haystack, (char*)needle));
haystack = "babbbbbabb";
needle = "bbab";
printf("%s, %s : %s\n", haystack, needle, strStr1((char*)haystack, (char*)needle));
if (argc>2){
haystack = argv[1];
needle = argv[2];
printf("%s, %s : %s\n", haystack, needle, strStr((char*)haystack, (char*)needle));
}
return 0;
}