leetcode/src/28.c at master · lennylxx/leetcode · GitHub

Name: leetcode/src/28.c at master · lennylxx/leetcode · GitHub
Rating: 4.8 (472 reviews)
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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* KMP algorithm */
voidgetNext(char*pattern, int*next) {
if (pattern==NULL||next==NULL) return;

intm=strlen(pattern);
inti, j;
next[0] =0;
j=0;
for (i=1; i<m; i++) {
while (j>0&&pattern[i] !=pattern[j])
j=next[j-1];

if (pattern[i] ==pattern[j]) j++;

next[i] =j;
 }
}

intstrStr(char*haystack, char*needle) {
if (haystack==NULL||needle==NULL) return0;

intn=strlen(haystack);
intm=strlen(needle);

if (m==0) return0;

int*next= (int*)calloc(m, sizeof(int));

getNext(needle, next);
intans=-1;
inti, j;
j=0;
for (i=0; i<n; i++) {
while (j>0&&haystack[i] !=needle[j])
j=next[j-1];

if (haystack[i] ==needle[j]) j++;

if (j==m) {
ans=i+1-j;
break; /* if you want to continue search, comment out break */
j=next[j-1];
 }
 }

free(next);
returnans;
}

/* Brute force */
intstrStr0(char*haystack, char*needle) {
if (haystack==NULL||needle==NULL) return0;

intn=strlen(haystack);
intm=strlen(needle);

if (m==0) return0;

intans=-1;
inti, j;
j=0;
for (i=0; i<n; i++) {
while (j>0&&haystack[i] !=needle[j]) {
i=i+1-j;
j=0;
 }

if (haystack[i] ==needle[j]) j++;

if (j==m) {
ans=i+1-j;
break; /* if you want to continue search, comment out break */
j=0;
 }
 }

returnans;
}

intmain() {
charstr[] ="abcdacabcdabdeabcdabd";
charpattern[] ="abcdabd";

/* 6 */
printf("%d\n", strStr(str, pattern));

/* 0 */
printf("%d\n", strStr("", ""));

/* 0 */
printf("%d\n", strStr("1", ""));

return0;
}