forked from TheAlgorithms/C
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path28.c
More file actions
120 lines (101 loc) · 2.24 KB
/
Copy path28.c
File metadata and controls
120 lines (101 loc) · 2.24 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
/*
* brute force approach
* time complexity: O(mn)
*/
int strStr(char *haystack, char *needle)
{
int i = 0;
int j = 0;
int k = 0;
int hlen = 0;
int nlen = 0;
if (needle == NULL || *needle == 0)
return 0;
if (haystack == NULL || *haystack == 0)
return -1;
hlen = strlen(haystack);
nlen = strlen(needle);
if (hlen < nlen)
return -1;
for (i = 0; i <= hlen - nlen; i++)
{
j = 0;
if (haystack[i] != needle[j++])
continue;
k = i + 1;
for (; j < nlen; j++)
{
if (haystack[k] != needle[j])
{
break;
}
else
k++;
}
if (j == nlen)
return i;
}
return -1;
}
/* ----------------------------------------------------------------------------------------
*/
/*
* KMP algorithm
* time complexity: O(m + n)
*/
/* fills overlap with longest proper prefix which is also suffix for each index
* in needle */
void fill_overlap(char *needle, int len_needle, int *overlap)
{
int len = 0;
int i = 0;
overlap[0] = 0;
for (i = 1; i < len_needle;)
{
if (needle[i] == needle[len])
{
len++;
overlap[i++] = len;
}
else
{
if (len)
len = overlap[len - 1];
else
overlap[i++] = 0;
}
}
}
int strStr(char *haystack, char *needle)
{
int i = 0; /* index for haystack */
int j = 0; /* index for needle */
int len_needle = strlen(needle);
int len_haystack = strlen(haystack);
if (!len_needle)
return 0;
int overlap[len_needle];
fill_overlap(needle, len_needle, overlap);
while (i < len_haystack)
{
if (needle[j] == haystack[i])
{
i++;
j++;
}
if (j == len_needle)
{
return (i - j);
}
else if (i < len_haystack && needle[j] != haystack[i])
{
if (j != 0)
j = overlap[j - 1];
else
i = i + 1;
}
}
return -1;
}
/* ----------------------------------------------------------------------------------------
*/